回溯与DFS_回溯和dfs的区别

一丶DFS

深度优先搜索（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法

二丶回溯法=DFS+剪枝

适用于组合数相当大按 [深度优先策略] ，根节点出发搜索空间树，搜索任意节点是否包含问题的解，不包含回溯，否则，继续进行深度优先搜索
通过 [剪枝函数] 约束条件 (constraint) 在扩展结点处减去不满足约束的子树；用限界函数（bound）剪去得不到最优解的子树（假如我们只需要最优解的时候用） 避免不必要搜索的穷举式搜索

回溯法模板

vector<int> res; //解空间
void backtrack(int i){
	//若不符合约束和限界 return
	if(!bound(i)&&!constraint(i)) return;
	//搜索到空间树的叶子节点，添加一个可行解
	if(i>=n){
		res.push_back(str); return;
	}
    // 对解空间树的所有分枝（抽象为所有邻接点）一一搜索
    //上界与下界形成解空间树的数量
    for(int j=下界;j<=上界;j++){
    	backtrack(i+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意点：
树和图的邻接点很好想就很直接

1. 假如N皇后就是当前行的每一列

for (int i = 1; i <= n; i++) {
      x[t] = i;
      if (place(t)) backtrack(t + 1,n);
}
1
2
3
4

2. 迷宫那就是上下左右

 find(x - 1 , y);   
 find(x + 1 , y);       
 find(x , y - 1);
 find(x , y + 1);
1
2
3
4

3. 假如是生成子集就是当前字符选和不选

t.push_back(nums[cur]);
dfs(cur + 1, nums);
t.pop_back();
dfs(cur + 1, nums);
1
2
3
4

分支不是很多就不必要写成for循环，可以枚举出来就像迷宫和子集

还需要注意的是标记i和判断是否标记，这种一般用于类似于图结构，因为不同的点可能拥有相同的邻接点，回溯回来可能会再次相遇
上面的模板看起来没有标记其实是有的，因为for循环保证了依次访问，但是图的话就不能保证了

三丶区别（引用自链接）

回溯是一种更通用的算法。可以用于任何类型的结构，其中可以消除域的部分 ——无论它是否是逻辑树。

深度优先搜索是与搜索树或图结构相关的特定回溯形式。它使用回溯作为其使用树的方法的一部分，但仅限于树/图结构。

回溯和 DFS 之间的区别在于回溯处理隐式树而 DFS 处理显式树。这似乎微不足道，但它意味着很多。当通过回溯访问问题的搜索空间时，隐式树在其中间被遍历和修剪。然而对于 DFS 来说，它处理的树/图是明确构造的，并且在完成任何搜索之前已经抛出了不可接受的情况，即修剪掉了。

class Solution {
public:
    vector<vector<int>> res;
    void backtrack(int i,vector<int>& nums,vector<int> tmp){
        if(i==nums.size()){
            res.push_back(tmp);
            return;
        }
        backtrack(i+1,nums,tmp);
        tmp.push_back(nums[i]);
        backtrack(i+1,nums,tmp);

    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> tmp;
        backtrack(0,nums,tmp);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<vector<int>> res;
          
    void backtrack(int i,int cur,int n,int k,vector<int> tmp){
        if(i==k){
            res.push_back(tmp);
            return;
        }
        for(int j=cur;j<=n;j++){
            tmp.push_back(j);
            backtrack(i+1,j+1,n,k,tmp);
            tmp.pop_back();
            
          
        }
    }
    vector<vector<int>> combine(int n, int k) {
  		vector<int> tmp;
        backtrack(0,1,n,k);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

同一层的用完要复原 集合可以先不选就不用了复原了，但是组合总和要选，所以需要复原，有时候传值过程其实是最费时间的，使用引用或者公共多一些pop操作更快

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmp;
    void backtrack(int cur,vector<int>& candidates,int start){
        if(cur<0) return;
        if(cur==0){
            res.push_back(tmp);
            return;
        }
        for(int i=start;i<candidates.size();i++){
            tmp.push_back(candidates[i]);
            backtrack(cur-candidates[i],candidates,i);
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtrack(target,candidates,0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这个组合和上一个一样的用法作用不同：上一个不能多次选，这一个是保证结果不重复

class Solution {
public:
    vector<vector<int>> res;
          vector<int> tmp;
    void backtrack(int i,int cur,int n,int k){
        if(i==k){
            res.push_back(tmp);
            return;
        }
        for(int j=cur;j<=n;j++){
            tmp.push_back(j);
            backtrack(i+1,j+1,n,k);
            tmp.pop_back();
            
          
        }
    }
    vector<vector<int>> combine(int n, int k) {
  
        backtrack(0,1,n,k);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {   
        func("", 0, 0, n);
        return res;
    }
    
    void func( string str, int l, int r, int n){
        if(l > n || r > n || r > l) return ;
        if(l == n && r == n) {res.push_back(str); return;}
        func( str + '(', l+1, r, n);
        func( str + ')', l, r+1, n);
        return;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16