回溯算法part05 算法

回溯算法part05 算法

今日任务

• 491.递增子序列
• 46.全排列
• 47.全排列 II

1.LeetCode 491.递增子序列

https://leetcode.cn/problems/non-decreasing-subsequences/description/

class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backtracing(nums,0);return result;}public void backtracing(int[] nums,int startIndex){if(path.size()>=2){//一维加进2维的，究竟符不符合条件在单层那里处理result.add(new ArrayList<>(path));}HashSet<Integer> set=new HashSet<>();for(int i=startIndex;i<nums.length;i++){if(!path.isEmpty()&&path.get(path.size()-1)>nums[i]||set.contains(nums[i])){//这是处理横向的，没错//一维不为空&&一维集合最后一个元素值>现在遍历到的新元素值||hashset包含着现在遍历到的新元素值，证明是同一父节点下的同层上使用过的元素//第二个可以是[4,1,2,5],=>[4,5]//第三个同一父节点下的同层上使用过的元素就不能再使用了,因为这是处理横向的//[4,1,2,5,5]，[4,5] [4,5]这样就重复了，当然可以纵向，但是要避免横向不能重复continue;}//为空set.add(nums[i]);path.add(nums[i]);backtracing(nums,i+1);path.removeLast();}}
}

2.LeetCode 46.全排列

https://leetcode.cn/problems/permutations/

class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>();int[] used;//初始值默认都是0public List<List<Integer>> permute(int[] nums) {used=new int[nums.length];//初始值默认都是0backtracing(nums);return result;}public void backtracing(int[] nums){//终止条件，是到叶子节点时if(path.size()==nums.length){result.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;backtracing(nums);//深层的已经用完要变化used[i]=0;path.removeLast();}}
}

3.LeetCode 47.全排列 II

https://leetcode.cn/problems/permutations-ii/description/

//跟前一题有什么区别吗
//元素我重复了又如何，我是按照位置改的，又不是按照元素值
//事实证明，有区别，会出现重复的一维集合，需要过滤
class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>();int[] used;//初始值默认都是0public List<List<Integer>> permuteUnique(int[] nums) {used=new int[nums.length];//初始值默认都是0backtracing(nums);return result;}public void backtracing(int[] nums){//终止条件，是到叶子节点时if(path.size()==nums.length){result.add(new ArrayList<>(path));return;}HashSet<Integer> set=new HashSet<>();for(int i=0;i<nums.length;i++){//已经有这个来控制横向了//如果当前值没有被用过if(used[i]==1||set.contains(nums[i])){continue;}set.add(nums[i]);path.add(nums[i]);//标记为已经用过used[i]=1;backtracing(nums);//深层的已经用完要变化used[i]=0;path.removeLast();}}
}