代码随想录训练营二刷第二十九天 | 491.递增子序列 6.全排列 47.全排列 II

代码随想录训练营二刷第二十九天 | 491.递增子序列 6.全排列 47.全排列 II

一、491.递增子序列

题目链接：https://leetcode.cn/problems/non-decreasing-subsequences/
思路：本题数组是乱序的，要求收集递增子序列，有重复数字，但是要求结果集不能重复，还要求收集的递增子序列长度需要大于等于2.也就是除了根节点不收集其他节点都收集，要求收集递增子序列，那么每次往list中add数据时都要比较新值与list尾部的值，最后就是树层去重，由于不能排序，used数组或者比较i>index&&nums[i] == nums[i-1]就无法使用，上面那两个是排序后，相同的数贴在一块，对于3,7，6,7这种场景就无法应对。故去重选用set，在层间使用，每递归进入下一层就是一个新的set。

class Solution {
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> arrayLists = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return arrayLists;
    }

    void backTracking(int[] nums, int index) {
        if (list.size() > 1) {
            arrayLists.add(new ArrayList<>(list));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = index; i < nums.length; i++) {
            if (!list.isEmpty() && nums[i] < list.get(list.size()-1) || set.contains(nums[i])) continue;
            list.add(nums[i]);
            set.add(nums[i]);
            backTracking(nums, i + 1);
            list.remove(list.size()-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、6.全排列

题目链接：https://leetcode.cn/problems/permutations/
思路：不含重复元素，要求求全部排列，排列讲究顺序，如1,2，3。当第一次选了2之后，第二次递归还得能选择1，也就是不再需要指定横向for循环的开启位置了，每次都是从0开始，但是选过的数要记录，不能重复选，这就是纵向的，要求纵向不能重复选数，可以使用used数组，递归向下记录使用过，一回溯就是没使用过。

class Solution {
   List<List<Integer>> arrayLists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] used = null;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backTracking(nums);
        return arrayLists;
    }
    void backTracking(int[] nums) {
        if (list.size() == nums.length) {
            arrayLists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            list.add(nums[i]);
            used[i] = true;
            backTracking(nums);
            used[i] = false;
            list.remove(list.size()-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三、47.全排列 II

题目链接：https://leetcode.cn/problems/permutations-ii/
思路：for从0开始，避免纵向重复使用used数组记录，为true为使用过，为false为没使用过，即used[i]=true跳过，横向去重需要数组排序，当nums[i]=nums[i-1]时，used[i-1]=false是回溯完的，需要树层去重。

class Solution {
    List<List<Integer>> arrayLists = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] used = null;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return arrayLists;
    }
    void backTracking(int[] nums) {
        if (list.size() == nums.length) {
            arrayLists.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = true;
            list.add(nums[i]);
            backTracking(nums);
            used[i] = false;
            list.remove(list.size()-1);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26