47. Permutations II

Backtracking

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 {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        dfs(resultList, nums, 0);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, int[] nums, int levelIndex) {
        // 当到达最后一个元素时，即可收集，因为最后一个元素只能与自身交换
        if (levelIndex == nums.length - 1) {
            List<Integer> numList = new ArrayList<>(nums.length);
            for (int num : nums) {
                numList.add(num);
            }
            resultList.add(numList);
            return;
        }

        Set<Integer> set = new HashSet<>(); // 用于同层元素去重，如 [1, 2, 2], 其中 2 仅需被交换至索引 0 一次
        // 尝试将其他位置的元素交换至 levelIndex
        for (int i = levelIndex; i < nums.length; i++) {
            // 本层已经处理过 nums[i], 此时跳过
            if (!set.add(nums[i])) {
                continue;
            }

            swap(nums, i, levelIndex);
            dfs(resultList, nums, levelIndex + 1); // 进入下一层以固定下一位
            swap(nums, i, levelIndex);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Backtracking

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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        // 全排列与子集的区别在于全排列所有元素都是必须要用上的，而子集可以不选择其中一部分元素

        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>(nums.length);
        boolean[] used = new boolean[nums.length]; // 需要使用 used 数组是因为可以从任意一个数字作为起点，而不是必须从最小值的数字作为起点
        Arrays.sort(nums);
        backtrack(resultList, numList, nums, used);
        return resultList;
    }

    private void backtrack(List<List<Integer>> resultList, List<Integer> numList, int[] nums, boolean[] used) {
        if (numList.size() == nums.length) {
            resultList.add(new ArrayList<>(numList));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }

            // 同层去重
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }

            numList.add(nums[i]);
            used[i] = true;
            backtrack(resultList, numList, nums, used);
            numList.remove(numList.size() - 1);
            used[i] = false;
        }
    }
}

References

47. Permutations II
剑指 Offer 38. 字符串的排列
剑指 Offer II 084. 含有重复元素集合的全排列