1、题目
78题和46题可以一起看，一起做对比。两道题目都是用回溯算法求。但是递归参数有点区别。
78题：
image.png
46题：
image.png
2、分析
用回溯算法。可以结合后面的代码来看图
78题：
image.png
46题：
image.png
3、代码
78题代码：
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
LinkedList<Integer> tack = new LinkedList<>();
backTack(nums, 0, tack);
return res;
}
public void backTack(int[] nums, int start, LinkedList<Integer> tack){
res.add(new LinkedList<>(tack));
//从start开始循环
for(int i = start; i < nums.length; i++){
tack.add(nums[i]);
backTack(nums, i + 1, tack);
tack.removeLast();
}
}
}
46题代码：
class Solution {
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> tack = new LinkedList<>();
dfs(nums, tack);
return res;
}
private void dfs(int[] nums, LinkedList<Integer> tack){
if(tack.size() == nums.length){
res.add(new LinkedList<Integer>(tack));
return;
}
//每一次都从0开始循环
for(int i = 0; i < nums.length; i++){
if(tack.contains(nums[i])) continue;
tack.add(nums[i]);
dfs(nums, tack);
tack.removeLast();
}
}
}
