==本质上是一种枚举==

定义

从初始状态经过不确定的步数，到有条件的⽬标状态

每个状态有⼀种或多种⽅式到下⼀个状态（状态转移）

在过程中进⾏⼀定的判定，对⼀定不可能到⽬标状态的提前结束枚举（剪枝）

例一 ：组合数

给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// c++ 11
vector<vector<int>> ans;
vector<int> comb;
void traceback(){
    if(comb.size() == k){
        ans.push_back(comb);
        return;
    }
    int lower = comb.size() == 0 ? 1 : comb.back() + 1;
    for(int i = lower; i <= n;i ++){
        comb.push_back(i);
        traceback();
        comb.pop_back();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// c++ 17
vector<vector<int>> ans;
vector<int> comb;
auto traceback = [&](auto &self){
    if(comb.size() == k){
        ans.push_back(comb);
        return;
    }
    int lower = comb.size() == 0 ? 1 : comb.back() + 1;
    for(int i = lower; i <= n;i ++){
        comb.push_back(i);
        self(self);
        comb.pop_back();
    }
};

其实我们在枚举状态时，从back()+1开始枚举，⽽不是从1开始，就已经在剪枝了

当然，还可以有更好的剪枝，枚举的上界也可以优化，剩余还需要填充的个数是 k-comb.size()，如果我们当前选择x，那么最多可以选择[x,x+1,x+2,…n]也就是n-x+1个，如果⽐k-comb.size() ⼩，那么说明后续⼀定不可能组合成k个数字

所以上界n-x+1>=k-comb.size() 因此x<=n+1-k+comb.size()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 剪枝做法
vector<vector<int>> ans;
vector<int> comb;
auto traceback = [&](auto &self){
    if(comb.size() == k){
        ans.push_back(comb);
        return;
    }
    int lower = comb.size() == 0 ? 1 : comb.back() + 1;
    int upper = n + 1 - k + comb.size();
    for(int i = lower; i <= upper;i ++){
        comb.push_back(i);
        self(self);
        comb.pop_back();
    }
};

例二 ：幂集

一个整数数组nums，数组内元素各不相同，返回该数组幂集

解法一：可以在上题的基础上改进，相当于没有comb.size() == k的限制，每个答案都加入ans中

传递一个下界，每次递归枚举时，直接从上一个选择的元素下标开始枚举

1
2
3
4
5
6
7
8
9
10
vector<vector<int>> ans;
vector<int> subset;
auto traceback = [&](auto &self, int lower) -> void {
    ans.push_back(subset);
    for(int i = lower; i < nums.size(); i ++){
        subset.push_back(nums[i]);
        self(self, i + 1);
        subset.pop_back();
    }
};

==辅助状态：==其实subset已经可以表示完整的状态；如果不传递lower，可以循环找subset最后一个元素在原数组中的下标，然后从这个下标开始找，达到一样的效果；但每次都找一次，时间显然会更慢。因此通过辅助状态，来加速状态的转移

辅助状态是回溯中一个非常重要的概念，好的辅助状态可以极大的提高运行速度

解法二：把子集看做是否选择某个元素，因此对于每个位置，可以有两种状态转移的方式：选择 或 不选择

这种做法的状态是：当前子集、枚举到第几个元素

目标状态：枚举完所有元素 状态转移：选择 或 不选择

1
2
3
4
5
6
7
8
9
10
11
12
vector<vector<int>> ans;
vector<int> subset;
auto traceback = [&](auto &self, pos) {
    if(pos = nums.size()){
        ans.push_back(subset);
        return;
    }
    self(self, pos + 1);
    subset.push_back(nums[pos]);
    self(self, pos + 1);
    subset.pop_back();
};

上两个程序可见，subset, pos, lower都是状态，但是subset作为全局上下文，pos和lower作为参数传递；其实他们作为全局上下文或参数传递都可以。但一般而言，基础数据类型作为参数，非基础数据类型作为全局上下文会更方便编写

解法三：现在用一个二进制数字来表示选择的情况 71 -> 1000111，枚举[0, 2 ^ n-1]的情况来统计子集

用s >> i & 1判断这一位是选还是不选

1
2
3
4
5
6
7
8
9
10
int n = nums.size();
vector<vector<int>> ans;
for(int s = 0; s < (1 << n); s++){
    vector<int> sub;
    for(int i = 0; i < n; i++){
        if(s >> 1 & 1) sub.emplace_back(nums[i]);
    }
    ans.emplace_back(move(sub));
}
return ans;

启发：模板

1
2
3
4
5
6
7
8
9
10
traceback(state):
	if(check(state)):
		saveSolution(state) //判断到达目标状态
         return //可选
     for each candidates: //对于每个可能的转移
	 	if(illegality(state, candidate)): //非法状态
			continue
     	update(state, candidate) //更新状态
     	traceback(state) //状态转移
     	rollback(state, candidate) //回档，恢复之前的状态

例三：解数独

结论

1