47 Permutations II

47. Permutations II​
1. Question
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2]have the following unique permutations:
1
[
2
  [1,1,2],
3
  [1,2,1],
4
  [2,1,1]
5
]
Copied!
2. Implementation
(2) Backtracking
1
class Solution {
2
    public List<List<Integer>> permuteUnique(int[] nums) {
3
        List<List<Integer>> res = new ArrayList<>();
4
        List<Integer> permutation = new ArrayList<>();
5
        boolean[] used = new boolean[nums.length];
6
        Arrays.sort(nums);
7
        getPermutation(nums, used, permutation, res);
8
        return res;
9
    }
10
​
11
    public void getPermutation(int[] nums, boolean[] used, List<Integer> permutation, List<List<Integer>> res) {
12
        if (permutation.size() == nums.length) {
13
            res.add(new ArrayList<>(permutation));
14
            return;
15
        }
16
​
17
        for (int i = 0; i < nums.length; i++) {
18
            if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
19
                continue;
20
            }
21
​
22
            if (!used[i]) {
23
                used[i] = true;
24
                permutation.add(nums[i]);
25
                getPermutation(nums, used, permutation, res);
26
                permutation.remove(permutation.size() - 1);
27
                used[i] = false;
28
            }
29
        }
30
    }
31
}
Copied!
3. Time & Space Complexity
Backtracking: 时间复杂度O(n!), 空间复杂度O(n!)

46 Permutations

51 N-Queens

Last modified 2yr ago

Copy link

Contents

47. Permutations II

1. Question

2. Implementation

3. Time & Space Complexity

47. Permutations II​

1. Question

2. Implementation

3. Time & Space Complexity

47. Permutations II