Link to Question

MEDIUM

Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example

Input:

nums = [1,1,2]

Output:

[[1,1,2],[1,2,1],[2,1,1]]

Explanation:
All unique permutations of [1,1,2].

---

Constraints

• 1 ≤ nums.length ≤ 8
• -10 ≤ nums[i] ≤ 10

---

Solution: Backtracking

• Time Complexity: O(n! * n)
• Space Complexity: O(n!)

C++

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        function<void()> dfs = [&]() {
            if (path.size() == nums.size()) {
                res.push_back(path);
                return;
            }
            for (int i = 0; i < nums.size(); ++i) {
                if (used[i]) continue;
                if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
                used[i] = true;
                path.push_back(nums[i]);
                dfs();
                path.pop_back();
                used[i] = false;
            }
        };
        dfs();
        return res;
    }
};