Problem Statement

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

LeetCode:

• https://leetcode.com/problems/permutations-ii/description/

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

• 1 ≤ nums.length ≤ 8
  • The array nums will have at least 1 element and at most 8 elements.
  • This tells us the backtracking approach is allowed.
• -10 ≤ nums[i] ≤ 10
  • Each number in the array can range from -10 to +10.
  • That gives you a total of 21 possible integer values.
  • This is a small value range, which might allow:
    • Using hashing or frequency arrays for duplicates
    • Optimization tricks (like using unordered_map<int, int> or bool[21])

Examples

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
        ]

Different Approaches

1️⃣ Backtracking with Used Array and Skipping Duplicates

Intuition:

Unlike the regular permutations problem, this one allows duplicate values. If we apply the regular backtracking approach, we may get duplicate permutations in the result.

We must avoid generating duplicates — either by:

• Skipping over them intelligently during recursion, or
• Using a set to store only unique permutations

Approach:

1. Sort the array first.
2. Use a used[] boolean array to keep track of elements used in the current permutation.
3. When choosing the next element, skip if:
   1. It's the same as the previous, and
   2. The previous duplicate hasn't been used yet.

Code:

// Backtracking helper function to generate all unique permutations
void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& temp, vector<vector<int>>& res) {
    // Base case: if the current permutation (temp) has the same size as input,
    // we've found a complete and valid permutation
    if (temp.size() == nums.size()) {
        res.push_back(temp);  // Save the current permutation
        return;
    }

    // Iterate through all elements to choose the next one in the permutation
    for (int i = 0; i < nums.size(); ++i) {
        // Skip this number if it's already used in the current permutation
        if (used[i]) continue;

        // Skip duplicate numbers to avoid duplicate permutations
        // Condition: same value as previous AND previous one hasn't been used yet
        // This ensures we only take the first unused instance of a repeated number
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

        // Choose nums[i]
        used[i] = true;
        temp.push_back(nums[i]);

        // Recurse with the updated temp and used arrays
        backtrack(nums, used, temp, res);

        // Backtrack: undo the choice to explore other possibilities
        temp.pop_back();
        used[i] = false;
    }
}

// Main function to generate all unique permutations of nums
vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> res;                     // To store all unique permutations
    vector<int> temp;                            // Temporary vector to build current permutation
    vector<bool> used(nums.size(), false);       // Boolean vector to mark used elements

    sort(nums.begin(), nums.end());              // Sort the input to group duplicates together
                                                 // This is essential for duplicate skipping logic

    backtrack(nums, used, temp, res);            // Start the recursive backtracking
    return res;
}

Complexity Analysis:

• Time Complexity: O(n!)
  • We still explore all unique permutations.
• Space Complexity: O(n) recursion + O(n!) output.

2️⃣ Backtracking + HashSet at Each Level