回溯法-深度优先搜索(使用C++实现)

😲示例

回溯的本质是穷举, 即按照一定的顺序对元素进行排列组合找到所有可能情况, 随后筛选出需要的一个最优情况或者符合要求的多个情况

如果一个问题可以抽象成数学中的排列组合, 那么也可以使用回溯法来找到所有的排列组合, 其中, 排列不用去重, 组合需要去重

回溯法使用的搜索方式可以看作深度优先搜索, 即按一种方式搜索到尽头之后再回退

下面展示一种回溯法的经典写法

vector<vector<int>> result;     // 结果
vector<int> path;               // 路径
void dfs(......){               // 深度优先搜索
    if(......){                 // 终点条件
        result.push_back(path); // 添加这一次的路径
        return;                 // 向上回溯
    }
    for(int i=start; i<=n; i++){// 向下挨个搜索
        path.push_back(i);      // 添加一个节点
        dfs(n,k,i+1);           // 向下搜索
        path.pop_back();        // 回溯
    }
}

vector<vector<int>> ......(......){
    dfs(......);
    return result;
}

🤔一些疑问解答

如何对结果进行去重

如果允许对题干提供的数组进行打乱, 那么可以先排序再使用一个数组标记是否到达过该位置, 从而进行去重, 例如子集II
不论是否可以打乱数组都可以使用set方法进行去重, 因为set提供了find()方法进行O(1)复杂度的查找, 例如递增子序列

有没有什么方法能够把递归写法写成非递归写法?

💪力扣刷题

77. 组合

力扣传送门

class Solution {
    vector<vector<int>> result;     // 结果
    vector<int> path;               // 路径
private:
    void dfs(int n, int k, int start){  // 深度优先搜索
        if(path.size()==k){             // 终点条件
        result.push_back(path);         // 添加这一次的路径
        return;                         // 向上回溯
        for(int i=start; i<=n; i++){    // 向下挨个搜索
            path.push_back(i);          // 添加一个节点
            dfs(n,k,i+1);               // 向下搜索
            path.pop_back();            // 回溯
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(n,k,1);
        return result;
    }
};

17. 电话号码的字母组合

力扣传送门

class Solution {
private:
    const string letters_map[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> result;
    string s;
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return result;
        dfs(digits,0);
        return result;
    }
    void dfs(string& digits, int index){
        if(index==digits.size()){
            result.push_back(s);
            return;
        }
        string temp = letters_map[digits[index]-'0'];
        int len = temp.size();
        for(int i=0; i<len; i++){
            s.push_back(temp[i]);
            dfs(digits,index+1);
            s.pop_back();
        }
    }
};

39. 组合总和

力扣传送门

class Solution {
private:
    vector<vector<int>> result;
    vector<int> temp;
    void dfs(vector<int>& candidates, int target, int sum, int start){
        if(target==sum){
            result.push_back(temp);
            return;
        }
        if(sum>target){
            return;
        }
        int len = candidates.size();
        for(int i=start; i<len && sum+candidates[i]<=target; i++){
            temp.push_back(candidates[i]);
            dfs(candidates,target,sum+candidates[i],i);
            temp.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates, target, 0, 0);
        return result;
    }
};

131. 分割回文串

力扣传送门

class Solution {
private:
    vector<vector<string>> result;
    vector<string> temp;
    bool judge(string& s, int start, int end){
        while(start<end){
            if(s[start]!=s[end])
                return false;
            start++;
            end--;
        }
        return true;
    }
    void dfs(string& s, int start){
        int len = s.size();
        if(start==len){
            result.push_back(temp);
            return;
        }
        for(int i=start; i<len; i++){
            if(judge(s, start, i)){
                string str = s.substr(start,i-start+1);
                temp.push_back(str);
                dfs(s,i+1);
                temp.pop_back();
            }
        }
    }
public:
    vector<vector<string>> partition(string s) {
        dfs(s,0);
        return result;
    }
};

78. 子集

力扣传送门

class Solution {
private:
    vector<vector<int>> result;
    vector<int> temp;
    void dfs(vector<int>& nums, int start){
        int len = nums.size();
        if(start==len)
            return;
        for(int i=start; i<len; i++){
            temp.push_back(nums[i]);
            result.push_back(temp);
            dfs(nums,i+1);
            temp.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.push_back(temp);
        dfs(nums,0);
        return result;
    }
};

90. 子集 II

传送门

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& nums, vector<bool> arrived, int start){
        result.push_back(path);         // 每次路径增加都需要记录为一种结果
        for(int i=start; i<nums.size(); i++){
            if(i>0 && nums[i]==nums[i-1] && !arrived[i-1])  // 去重, 如果同一层有相同的数取过, 那么这一次不再取相同的数
                continue;
            arrived[i] = true;      // 增加路径元素
            path.push_back(nums[i]);
            dfs(nums,arrived,i+1);
            path.pop_back();
            arrived[i] = false;
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool> arrived(nums.size(),false);    // 记录是否到达
        sort(nums.begin(),nums.end());              // 排序
        dfs(nums,arrived,0);                        // 搜索
        return result;
    }
};

40. 组合总和 II

传送门

本解法效率较低

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& candidates,vector<bool> arrived, int sum, int target, int start){
        if(sum==target){
            result.push_back(path);
            return;
        }
        if(sum>target)
            return;
        for(int i=start; i<candidates.size(); i++){
            if(i>0 && candidates[i]==candidates[i-1] && !arrived[i-1])
                continue;
            arrived[i] = true;
            path.push_back(candidates[i]);
            dfs(candidates,arrived,sum+candidates[i],target,i+1);
            path.pop_back();
            arrived[i] = false;
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<bool> arrived(candidates.size(),false);
        dfs(candidates,arrived,0,target,0);
        return result;
    }
};

491. 递增子序列

传送门

方法一 找到符合要求能加入路径中的数, 然后加入路径

for(int i=start; i<nums.size(); i++){
    if((path.empty() || path.back()<=nums[i]) && uset.find(nums[i])==uset.end()){
        uset.insert(nums[i]);
        path.push_back(nums[i]);
        dfs(nums,i+1);
        path.pop_back();
    }
}

方法二 或者是找到不符合要求不能加入路径中的数, 跳过

for (int i = start; i<nums.size(); i++) {
    if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end())
        continue;
    uset.insert(nums[i]); 
    path.push_back(nums[i]);
    backtracking(nums, i + 1);
    path.pop_back();
}

整体代码如下

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<int>& nums, int start){
        if(path.size()>=2)          // 长度大于2的序列
            result.push_back(path); // 记录
        if(start==nums.size())      // 如果寻找的索引值超过数组
            return;                 // 退出
        unordered_set<int> uset;    // 创建set用于在本层中去重
        for(int i=start; i<nums.size(); i++){
            if((path.empty() || path.back()<=nums[i]) && uset.find(nums[i])==uset.end()){       // 找到符合要求的nums[i]
                uset.insert(nums[i]);       // 加入set 
                path.push_back(nums[i]);
                dfs(nums,i+1);
                path.pop_back();
            }
        }
    }
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(nums,0);
        return result;
    }
};