Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]
Example 2:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8-10 <= nums[i] <= 10
Related Topics:
Array, Backtracking
Similar Questions:
- Next Permutation (Medium)
- Permutations (Medium)
- Palindrome Permutation II (Medium)
- Number of Squareful Arrays (Hard)
Similar idea as the DFS solution to 46. Permutations (Medium). We pick a number after A[i] and swap it with A[i] and don't swap back. So this new A[i] is the number we last
But since there are duplicates, we shouldn't swap the A[i] with the same digit twice.
The first idea is sorting the array and only swapping numbers A[j] != A[j-1] with A[i]. But this only works when the array after A[i] is sorted. After some swap, this might not be true.
To resolve this issue, one brute force way is to simply keep copying the array during DFS, which adds time and space complexity.
// OJ: https://leetcode.com/problems/permutations-ii
// Author: github.com/lzl124631x
// Time: O(N! * N)
// Space: O(N^2)
// Ref: https://discuss.leetcode.com/topic/8831/a-simple-c-solution-in-only-20-lines
class Solution {
private:
vector<vector<int>> ans;
void permute(vector<int> nums, int start) {
if (start == nums.size() - 1) {
ans.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
if (i != start && nums[i] == nums[start]) continue;
swap(nums[i], nums[start]);
permute(nums, start + 1);
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
permute(nums, 0);
return ans;
}
};Assume nums is sorted.
Consider the DFS solution to 46. Permutations. In each DFS level, assume the numbers starting from index start are sorted, then if nums[i] is the same as the number in front of itself, when nums[i] should be skipped because we've used the same number before.
For example, start = 0, nums = [1,1,2], i = 1, since nums[i] = 1 = nums[i - 1], it means that we already did DFS using nums[i - 1] so we shouldn't try to put nums[i] at nums[start].
If nums[i] is the first digit in the sequence of the same digit, we move it to nums[start] and DFS one step further.
And after that, we move it back from nums[start] to nums[i].
We can not just swap nums[i] and nums[start] because it will break the assumption that the numbers starting from index start are sorted. For example, start = 0, nums = [1, 1, 2, 2, 3, 3], i = 4, if we do swap we get [3, 1, 2, 2, 1, 3] which breaks the sorted assumption.
So we have to move the numbers one by one.
// OJ: https://leetcode.com/problems/permutations-ii
// Author: github.com/lzl124631x
// Time: O(N! * N)
// Space: O(N)
class Solution {
vector<vector<int>> ans;
void move(vector<int> &nums, int from, int to) {
int tmp = nums[from], d = from > to ? -1 : 1;
for (int i = from; i != to; i += d) nums[i] = nums[i + d];
nums[to] = tmp;
}
void permute(vector<int> &nums, int start) {
if (start == nums.size()) {
ans.push_back(nums);
return;
}
int prev = nums[start];
for (int i = start; i < nums.size(); ++i) {
if (i != start && nums[i] == prev) continue;
move(nums, i, start);
permute(nums, start + 1);
move(nums, start, i);
prev = nums[i];
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
permute(nums, 0);
return ans;
}
};Similar to Solution 2, based on the DFS solution to 46. Permutations.
But when we check whether the nums[i] is used before, we simply use a set to store the visited digits!
The logic of this code is way simpler. It's just that the set takes extra space.
// OJ: https://leetcode.com/problems/permutations-ii
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N^2)
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& A) {
vector<vector<int>> ans;
int N = A.size();
sort(begin(A), end(A));
function<void(int)> permute = [&](int i) {
if (i == N) {
ans.push_back(A);
return;
}
bool seen[21] = {};
for (int j = i; j < N; ++j) {
if (seen[A[j] + 10]) continue;
seen[A[j] + 10] = true;
swap(A[i], A[j]);
dfs(i + 1);
swap(A[i], A[j]);
}
};
dfs(0);
return ans;
}
};Based on the solution to 31. Next Permutation.
// OJ: https://leetcode.com/problems/permutations-ii
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(1)
class Solution {
private:
bool nextPermutation(vector<int> &nums) {
int i = nums.size() - 2, j = nums.size() - 1;
while (i >= 0 && nums[i] >= nums[i + 1]) --i;
if (i >= 0) {
while (j > i && nums[j] <= nums[i]) --j;
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
return i != -1;
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans { nums };
while (nextPermutation(nums)) ans.push_back(nums);
return ans;
}
};See explanations in https://youtu.be/nYFd7VHKyWQ
// OJ: https://leetcode.com/problems/permutations-ii
// Author: github.com/lzl124631x
// Time: O(N!)
// Space: O(N)
// Ref: https://youtu.be/nYFd7VHKyWQ
class Solution {
vector<int> cnt;
vector<int> digit;
vector<vector<int>> ans;
void dfs(vector<int> &nums, int start) {
if (start == nums.size()) {
ans.push_back(nums);
return;
}
for (int i = 0; i < cnt.size(); ++i) {
if (!cnt[i]) continue;
cnt[i]--;
nums[start] = digit[i];
dfs(nums, start + 1);
cnt[i]++;
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
map<int, int> m;
for (int n : nums) m[n]++;
for (auto p : m) {
digit.push_back(p.first);
cnt.push_back(p.second);
}
dfs(nums, 0);
return ans;
}
};