LeetCode算法训练-回溯 491.递增子序列 46.全排列 47.全排列 II

LeetCode算法训练-回溯 491.递增子序列 46.全排列 47.全排列 II

LeetCode 491. 递增子序列

分析

找出并返回所有数组中不同的递增子序列

• 绝对不能先升序 绝对不能先升序 绝对不能先升序 这样会改变原有数组的结构
  
• 子序列中元素在数组中不一定相邻
  
• 只要叶子节点，也就是path，一满足条件，直接加入res
  
• 注意去重used[] 数组只针对当前节点的后序节点 要在回溯函数中定义 画回溯树一看便知
  

代码

1. class Solution {
2.     private LinkedList<Integer> path = new LinkedList<>();
3.     private List<List<Integer>> res = new ArrayList<>();
4.     public List<List<Integer>> findSubsequences(int[] nums) {
5.         backtracking(nums,0);
6.         return res;
7.     }
9.     private void backtracking (int[] nums, int start) {
10.         // 保证了能进入path的元素是升序的
11.         if (path.size() > 1) {
12.             res.add(new LinkedList<>(path));
13.             // 注意这里不要加return，要取树上的节点
14.         }
15.         // 元素值为used数组索引 只对同一行进行去重
16.         int[] used = new int[201];
17.         for (int i = start; i < nums.length; i++) {
18.             // path 为空 当前元素小于path最后一个元素 或者这个元素在本层已经使用过了 跳过这个继续横向遍历
19.             if (!path.isEmpty() && nums[i] < path.getLast() || (used[nums[i] + 100] == 1)) {
20.                     // 如果是break 应该是终止当前节点的横向遍历 进入递归
21.                     continue;
22.                 }
23.             used[nums[i] + 100] = 1;
24.             path.add(nums[i]);
25.             backtracking(nums, i + 1);
26.             path.removeLast();
27.         }
28.     }
29. }

复制代码

LeetCode 46. 全排列

分析

全排列，收集回溯树的叶子节点即可 注意终止条件要return
But 因为搜索过程每次都从第一个元素开始，要记录哪些元素已经使用过了 used[]数组应该是全局的
代码

1. class Solution {
3.     List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
4.     LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
5.     boolean[] used;
6.     public List<List<Integer>> permute(int[] nums) {
7.         if (nums.length == 0){
8.             return result;
9.         }
10.         used = new boolean[nums.length];
11.         permuteHelper(nums);
12.         return result;
13.     }
15.     private void permuteHelper(int[] nums){
16.         if (path.size() == nums.length){
17.             result.add(new ArrayList<>(path));
18.             return;
19.         }
20.         for (int i = 0; i < nums.length; i++){
21.             if (used[i]){
22.                 continue;
23.             }
24.             used[i] = true;
25.             path.add(nums[i]);
26.             permuteHelper(nums);
27.             path.removeLast();
28.             used[i] = false;
29.         }
30.     }
31. }

复制代码

LeetCode 47. 全排列 II

分析

按任意顺序 返回所有不重复的全排列
涉及到如何去重 根据用例画一个回溯树看看
在横向遍历时，如果当前元素==前一个元素，continue；
难点：如何判断统一树层当前节点的前一个节点使用过 去看一下当前节点前一个节点的状态

1. if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
2.         continue;
3. }

复制代码

代码

1. class Solution {
3.     List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
4.     LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
5.    
6.     public List<List<Integer>> permuteUnique(int[] nums) {
7.         if (nums.length == 0){
8.             return result;
9.         }
10.         // 得先排个序才能保证前后元素比较的正确性
11.         Arrays.sort(nums);
12.         boolean[] used = new boolean[nums.length];
13.         permuteHelper(nums,used);
14.         return result;
15.     }
17.     private void permuteHelper(int[] nums, boolean[] used){
18.         if (path.size() == nums.length){
19.             result.add(new ArrayList<>(path));
20.             return;
21.         }
22.         for (int i = 0; i < nums.length; i++){
23.             // 一定要通过used保证nums[i-1]是树层上nums[i]的前一个元素
24.             if(i > 0 && nums[i] == nums[i-1] && !used[i-1]){
25.                 continue;
26.             }
27.             if (!used[i]){
28.                 used[i] = true;
29.                 path.add(nums[i]);
30.                 permuteHelper(nums,used);
31.                 path.removeLast();
32.                 used[i] = false;
33.             }
35.         }
36.     }
37. }

复制代码

总结

• 组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果
  
• 理清回溯树树层、树枝的节点关系 for循环处理的是树层，递归调用函数处理的是树枝
  
• 如果没有startIndex来确定取的是数组中哪一个元素，used[]数组+for循环能间接确定这个元素是不是取过
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！