14. 回溯
问自己三个问题：
- 当前操作应该是什么？
- 子问题是什么？
- 下一个子问题应该是什么？
14.1 Master公式
形如
$$
T(N) = a * T(\frac{N}{b}) + O(N^d)
$$
其中的a、b、d都是常数的递归函数，可以直接通过Master公式来确定时间复杂度
如果 log(b,a) < d，复杂度为O(N^d)
如果 log(b,a) > d，复杂度为O(N^log(b,a))
如果 log(b,a) == d，复杂度为O(N^d * logN)
14.1 子集型回溯
子集型回溯本质上就是看对于每一个元素，都可以选/不选。
14.1.1 所有子集
1. 题目
https://leetcode-cn.com/problems/subsets/
给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
2. 思路
方法1 ：从输入的角度考虑
对于[1,2]这个集合，站在输入的角度，每个数可以在子集中，也可以不在。
问自己：
- 当前操作：枚举第i个数，选/不选
- 子问题：从下表≥i的数字中构造子集
- 下一个子问题：从下表≥i+1的数字中构造子集
方法2：从答案的角度考虑
对于[1,2]这个集合，每次枚举第一个选谁，第二个选谁......
每个节点都是答案，但是[1,2]和[2,1]是同一个答案，要去重复
问自己：
- 当前操作：枚举下标 j ≥ i的数字，加入答案
- 子问题：从下表 ≥ i的数字中构造子集
- 下一个子问题？从下标 ≥ j + 1的数字中构造子集
3. 代码
输入角度考虑：
class Solution {
List<Integer> temp;
List<List<Integer>> ans;
public List<List<Integer>> subsets(int[] nums) {
temp = new ArrayList<>();
ans = new ArrayList<>();
dfs(nums,0);
return ans;
}
public void dfs(int[] nums, int depth){
int len = nums.length;
if(depth == len){
// 新建一个拷贝数组
ans.add(new ArrayList<Integer>(temp));
return;
}
// 不选
dfs(nums,depth+1);
// 选择
temp.add(nums[depth]);
dfs(nums,depth+1);
// 删除就删除最后一个，remove(index) - 是index不是值
temp.remove(temp.size()-1);
}
}
从答案考虑：
class Solution {
List<Integer> temp;
List<List<Integer>> ans;
public List<List<Integer>> subsets(int[] nums) {
temp = new ArrayList<>();
ans = new ArrayList<>();
dfs(nums,0);
return ans;
}
// 从答案的角度：每次选择不回退，每个都是答案
public void dfs(int[] nums, int index){
ans.add(new ArrayList<>(temp));
int len = nums.length;
for(int i = index; i < len; i++){
temp.add(nums[i]);
dfs(nums,i+1);
temp.remove(temp.size()-1);
}
}
}
14.2 组合型回溯
14.2.1 含有k个元素的组合
1. 题目
https://leetcode-cn.com/problems/combinations/
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例 1:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2:
输入: n = 1, k = 1
输出: [[1]]
2. 思路
跟之前的子集型回溯，从答案思考相似，但是增加一点判断条件即可。
注意：如果当前位置i+k后已经大于了n，也就是后面无解，不用遍历了。
为了保证无重复，只允许一个方向的遍历（比如[3,2,1]，遍历了2不允许回到3）。
2. 代码
class Solution {
List<List<Integer>> res;
List<Integer> temp;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
temp = new ArrayList<>();
dfs(1,k,n);
return res;
}
public void dfs(int index, int k, int n){
if(temp.size() == k) {
res.add(new ArrayList<Integer>(temp));
return;
}
// 剩下的数如果小于k个了，返回
// 剩下的数为：1 2 3 4 5 比如n=5，index = 3，此时剩下234三个数
// 剩下的数 < k - 已经选了的数
// 倒叙更简单，可以看灵神的倒叙
if(n - index + 1 < k - temp.size()) return;
// 加index后的所有，如果加过了某一个i，就不能再加前面的了
for(int i = index; i <= n; i++){
temp.add(i);
dfs(i+1,k,n);
temp.remove(temp.size()-1);
}
}
}
14.3 排列型回溯
14.3.1 没有重复元素集合的全排列
1. 题目
https://leetcode-cn.com/problems/permutations/
给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
2. 思路
问问自己：
- 当前操作：从s中枚举要填入的数字
- 子问题：构造排列≥i的部分，剩余部分未选的集合为s
- 下一个子问题：构造排列 ≥ i+1的部分，剩余未选集合为s-
3. 代码
class Solution {
List<List<Integer>> res;
List<Integer> temp;
public List<List<Integer>> permute(int[] nums) {
res = new ArrayList<>();
temp = new ArrayList<>();
int[] isVisit = new int[nums.length];
dfs(0,isVisit,nums);
return res;
}
// 第i个位置需要填数，已经被选过的位置，数组nums
public void dfs(int index,int[] isVisit, int[]nums){
// dfs一定会选中一个，这样就不需要判断index之前有没有没被选中的情况
if(index == nums.length){
res.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(isVisit[i] == 1) continue;
isVisit[i] = 1;
temp.add(nums[i]);
dfs(index+1,isVisit,nums);
temp.remove(temp.size()-1);
isVisit[i] = 0;
}
}
}