算法笔记|Day22回溯算法IV

☆☆☆☆☆leetcode 491.递增子序列

题目链接：leetcode 491.递增子序列

题目分析

本题求自增子序列，是不能对原数组进行排序的，排完序的数组都是自增子序列了，可以用数组来做哈希。注意used数组是记录本层元素是否重复使用，新的一层used都会重新定义（清空），所以要知道used只负责本层，回溯并不需要赋值恢复。

代码

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracking(nums,0);return res;}public void backtracking(int nums[],int start){int used[]=new int[201];        if(path.size()>1)res.add(new ArrayList(path));for(int i=start;i<nums.length;i++){if(!path.isEmpty()&&nums[i]<path.get(path.size()-1)||used[nums[i]+100]==1)continue;path.add(nums[i]);used[nums[i]+100]=1;backtracking(nums,i+1);path.remove(path.size()-1);}}
}

☆☆☆☆☆leetcode 46.全排列

题目链接：leetcode 46.全排列

题目分析

排列问题仍然可以使用回溯，同样使用used数组，记录此时path里都有哪些元素使用，一个排列里一个元素只能使用一次。

代码

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> permute(int[] nums) {int used[]=new int[nums.length];backtracking(nums,used);return res;}public void backtracking(int nums[],int used[]){if(path.size()==nums.length){res.add(new ArrayList(path));return;}for(int i=0;i<nums.length;i++){if(used[i]==1)continue;path.add(nums[i]);used[i]=1;backtracking(nums,used);path.remove(path.size()-1);used[i]=0;}}
}

☆☆☆☆☆leetcode 47.全排列II

题目链接：leetcode 47.全排列II

题目分析

所求排列不能重复，需要去重的逻辑，对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用。另外，注意到对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

代码

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path=new LinkedList<>();public List<List<Integer>> permuteUnique(int[] nums) {Arrays.sort(nums);int used[]=new int[nums.length];backtracking(nums,used);return res;}public void backtracking(int nums[],int used[]){if(path.size()==nums.length){res.add(new ArrayList(path));return;}for(int i=0;i<nums.length;i++){if(used[i]==1)continue;if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)continue;path.add(nums[i]);used[i]=1;backtracking(nums,used);path.remove(path.size()-1);used[i]=0;}}
}

提示：
去重逻辑中：
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0)//树层去重
continue;
改为
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==1)//树枝去重
continue;
效果相同。

☆☆☆☆☆leetcode 332.重新安排行程（待补充）

题目链接：leetcode 332.重新安排行程

题目分析

代码

☆☆☆☆☆leetcode 51. N皇后（待补充）

题目链接：leetcode 51. N皇后

题目分析

代码

☆☆☆☆☆leetcode 37. 解数独（待补充）

题目链接：leetcode 37. 解数独

题目分析

代码