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;
}
}
}