前言

在做回溯时，常常遇到需要去重的情况，以及各种各样的条件限制。

万变不离其宗，只需要在回溯的 for 循环中第一行加入判断条件即可。

去重

排序去重

子集去重

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 对其进行排序
        Arrays.sort(nums);
        backtrack(nums, 0);
        return res;
    }

    private void backtrack(int[] nums, int start) {
        res.add(new ArrayList<>(path));

        for (int i = start; i < nums.length; i++) {
            // 判断前一个是否和后一个一样，一样就是用过了，跳过
            if(i > start && nums[i] == nums[i - 1]) continue;
            path.add(nums[i]);
            backtrack(nums, i + 1);
            path.removeLast();
        }
    }
}

HashSet 去重

递增子序列去重

因为原数组没法动，要直接找到里面递增的子序列，所以没法直接排序

用到了 HashSet

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
27
28
29
30
class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();


    public List<List<Integer>> findSubsequences(int[] nums) {
        backtrack(nums, 0);
        return res;
    }

    private void backtrack(int[] nums, int start){
        if(path.size() > 1){
            res.add(new ArrayList<>(path));
        }

        // 在每一层中进行去重
        Set<Integer> set = new HashSet<>();

        for(int i = start; i < nums.length; i++){
            // 如果之前用过了，就跳过
            if(!path.isEmpty() && path.getLast() > nums[i] || set.contains(nums[i])) continue;

            set.add(nums[i]);

            path.add(nums[i]);
            backtrack(nums, i + 1);
            path.removeLast();
        }
    }
}

更多的条件

全排列去重

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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private LinkedList<Integer> path = new LinkedList<>();
    // 记录数组中被使用过的数
    private boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length == 0) return res;
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }

    private void backtrack(int[] nums){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
        }

        // 记录这一层中被用过的数
        Set<Integer> set = new HashSet<>();

        for(int i = 0; i < nums.length; i++){
            // 如果已经加入了 path，就跳过
            // 或者这一层中已经有相同的数被用过了，就跳过
            if(used[i] == true || set.contains(nums[i])) continue;

            set.add(nums[i]);

            used[i] = true;
            path.add(nums[i]);

            backtrack(nums);

            path.removeLast();
            used[i] = false;
        }
    }
}