47. Permutations II
1. Description
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
2. Example
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]]
3. Constraints
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
4. Solutions
Backtracking
n = nums.size()
Time complexity: O(nn!)
Space complexity: O(n)
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int> nums) {
vector<vector<int>> result;
permute(nums, 0, result);
return result;
}
private:
void permute(vector<int> &nums, int index, vector<vector<int>> &result) {
if (index < nums.size()) {
map<int, bool> visit;
for (int i = index; i < nums.size(); ++i) {
if (!visit[nums[i]]) {
visit[nums[i]] = true;
swap(nums[i], nums[index]);
permute(nums, index + 1, result);
swap(nums[i], nums[index]);
}
}
} else {
result.push_back(nums);
}
}
};