1蚊荣、題目
78題和46題可以一起看，一起做對比莫杈。兩道題目都是用回溯算法求互例。但是遞歸參數(shù)有點區(qū)別。
78題：
image.png
46題：
image.png
2筝闹、分析
用回溯算法媳叨。可以結(jié)合后面的代碼來看圖
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開始循環(huán)
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開始循環(huán)
for(int i = 0; i < nums.length; i++){
if(tack.contains(nums[i])) continue;
tack.add(nums[i]);
dfs(nums, tack);
tack.removeLast();
}
}
}
