# Permutations II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/permutations-ii)
Canonical: https://scaleengineer.com/dsa/problems/permutations-ii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [TikTok](https://scaleengineer.com/companies/tiktok), [Citadel](https://scaleengineer.com/companies/citadel)
---
## Problem
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`

# Approaches
## Brute-force Backtracking with Set
This approach uses a standard permutation generation algorithm and relies on a `HashSet` to filter out the duplicate permutations. It explores all possible orderings of the elements, even if they lead to permutations that have already been found, and lets the properties of the set handle the uniqueness requirement.
**Time:** O(N * N!) · **Space:** O(N * P + N)
**Pros:** Conceptually simple to understand if familiar with the basic permutation algorithm.; The logic for handling duplicates is offloaded to the `HashSet`, simplifying the recursive part.
**Cons:** Highly inefficient as it generates many duplicate permutations which are then discarded.; The time complexity is factorial, O(N * N!), which is very slow for larger N.; High space complexity due to storing all unique permutations in a hash set, O(N * N!).
### Explanation
The core idea is to generate every single permutation as if all elements were distinct and then filter out the duplicates. We can use a recursive backtracking method with a `used` boolean array to keep track of the elements that have been placed in the current permutation. 

The recursive function builds a permutation step-by-step. At each step, it iterates through all the numbers in the input array. If a number hasn't been used yet, it's added to the current permutation, and the function calls itself to place the next number. Once a permutation is complete (its size equals the input array's size), it's added to a `HashSet`. The `HashSet` ensures that only unique lists are stored. This process continues until all possible permutations have been generated. Finally, the set of unique permutations is converted to a list.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Set<List<Integer>> resultSet = new HashSet<>();
        boolean[] used = new boolean[nums.length];
        backtrack(new ArrayList<>(), nums, used, resultSet);
        return new ArrayList<>(resultSet);
    }

    private void backtrack(List<Integer> currentPermutation, int[] nums, boolean[] used, Set<List<Integer>> resultSet) {
        if (currentPermutation.size() == nums.length) {
            resultSet.add(new ArrayList<>(currentPermutation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                currentPermutation.add(nums[i]);
                backtrack(currentPermutation, nums, used, resultSet);
                currentPermutation.remove(currentPermutation.size() - 1);
                used[i] = false; // backtrack
            }
        }
    }
}
```
### Algorithm
- Create a `HashSet<List<Integer>>` to store the unique permutations.
- Use a standard recursive backtracking function that generates all permutations (including duplicates) by picking numbers for the current permutation.
- The recursive function `backtrack(currentPermutation, nums, used, resultSet)` takes the permutation being built, the original numbers, a boolean `used` array to track usage, and the result set.
- **Base Case:** If the `currentPermutation`'s size equals the length of `nums`, a full permutation is formed. Add a copy of it to the `resultSet`. The set will automatically discard duplicates.
- **Recursive Step:** Iterate through all numbers in the `nums` array. If a number at index `i` has not been used (`!used[i]`):
  - Mark it as used (`used[i] = true`).
  - Add `nums[i]` to `currentPermutation`.
  - Make a recursive call: `backtrack(...)`.
  - Backtrack by removing the number from `currentPermutation` and un-marking it as used (`used[i] = false`).
- After the initial call completes, convert the `resultSet` to an `ArrayList` and return it.

## Backtracking with Frequency Map
This approach avoids generating duplicate permutations from the start by building them using the counts of each unique number. It constructs permutations by choosing from the available unique numbers at each step, ensuring no redundant paths are explored.
**Time:** O(N * P) · **Space:** O(N)
**Pros:** Efficiently prunes the search space by not exploring branches that lead to duplicate permutations.; Does not require sorting the input array.
**Cons:** Requires extra space for the frequency map.; The overhead of map operations might be slightly higher than array-based operations in other approaches.
### Explanation
Instead of permuting the elements of the array directly, we first process the array to find the unique numbers and their frequencies. This is typically done using a hash map. Then, a backtracking function is used to build the permutations. 

The function constructs a permutation one element at a time. At each level of the recursion, it iterates through the unique numbers from the frequency map. If a number's count is positive, it means it's available to be used. The number is added to the current permutation, its count is decremented, and a recursive call is made to find the next element. After the call returns, we backtrack by removing the number and restoring its count in the map. This allows the same number to be used at different positions in other permutations. Because we are choosing from unique numbers at each step, we inherently avoid creating duplicate permutations.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        backtrack(new LinkedList<>(), nums.length, counts, result);
        return result;
    }

    private void backtrack(LinkedList<Integer> currentPermutation, int n, Map<Integer, Integer> counts, List<List<Integer>> result) {
        if (currentPermutation.size() == n) {
            result.add(new ArrayList<>(currentPermutation));
            return;
        }

        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int num = entry.getKey();
            int count = entry.getValue();
            if (count > 0) {
                currentPermutation.addLast(num);
                counts.put(num, count - 1);

                backtrack(currentPermutation, n, counts, result);

                counts.put(num, count); // backtrack
                currentPermutation.removeLast();
            }
        }
    }
}
```
### Algorithm
- First, create a frequency map (e.g., a `HashMap`) to count the occurrences of each number in the input `nums` array.
- Define a recursive function `backtrack(currentPermutation, n, counts, result)`.
- **Base Case:** If the size of `currentPermutation` equals `n` (the total number of elements), a unique permutation has been formed. Add a copy of it to the `result` list.
- **Recursive Step:** Iterate through the unique numbers (the keys) in the frequency map.
  - For each number `num`, if its count is greater than 0:
    - Add `num` to the `currentPermutation`.
    - Decrement its count in the map.
    - Make a recursive call: `backtrack(...)`.
    - Backtrack by restoring the count of `num` in the map and removing it from `currentPermutation`.

## Optimized Backtracking with Sorting
This is a highly efficient and elegant approach that combines sorting with backtracking. By sorting the input array, duplicate elements become adjacent. This allows for a simple check within the recursive function to prune branches of the search tree that would lead to duplicate permutations, ensuring each unique permutation is generated exactly once.
**Time:** O(N * P) · **Space:** O(N)
**Pros:** Very efficient in both time and space.; Considered a standard and elegant solution for this type of problem.; Avoids the overhead of hash map operations.
**Cons:** Requires modifying the input by sorting, or creating a sorted copy which uses extra space.; The condition to skip duplicates (`!used[i-1]`) can be subtle and tricky to reason about initially.
### Explanation
This method refines the standard backtracking algorithm. The first step is to sort the input array `nums`. This is crucial because it groups all identical numbers together. The backtracking function then proceeds to build a permutation, using a boolean `used` array to keep track of which elements (by their original index) are already in the permutation.

The magic happens in the loop that picks the next number. In addition to the standard check to see if an element `used[i]` has been used, we add another condition: if the current number `nums[i]` is the same as the previous one `nums[i-1]`, we only consider using `nums[i]` if `nums[i-1]` has *already* been used. If `nums[i-1]` was not used, it means the permutation that would have been formed by picking `nums[i-1]` at this level has been (or will be) generated in a different path. By skipping `nums[i]` in this case, we enforce an ordering on picking duplicate elements, which effectively eliminates the generation of duplicate permutations.

```java
import java.util.*;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(new ArrayList<>(), nums, new boolean[nums.length], result);
        return result;
    }

    private void backtrack(List<Integer> currentPermutation, int[] nums, boolean[] used, List<List<Integer>> result) {
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            // If the current element is a duplicate of the previous one,
            // and the previous one hasn't been used in this path, skip.
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            used[i] = true;
            currentPermutation.add(nums[i]);
            backtrack(currentPermutation, nums, used, result);
            currentPermutation.remove(currentPermutation.size() - 1);
            used[i] = false; // backtrack
        }
    }
}
```
### Algorithm
- First, sort the input `nums` array. This brings all duplicate numbers together.
- Use a standard backtracking function with a `used` boolean array to track which indices have been included in the current permutation.
- **Base Case:** If the current permutation's size equals the length of `nums`, add a copy to the result list.
- **Recursive Step:** Iterate through the `nums` array from `i = 0` to `n-1`.
  - **Skip Condition 1:** If `used[i]` is true, the element is already in the current permutation, so `continue`.
  - **Skip Condition 2 (Key Optimization):** If `i > 0` and the current element `nums[i]` is the same as the previous element `nums[i-1]`, AND the previous element has not been used yet (`!used[i-1]`), then `continue`. This prevents generating duplicate permutations.
  - If the element is not skipped:
    - Mark `used[i] = true`.
    - Add `nums[i]` to the current permutation.
    - Recurse.
    - Backtrack by un-marking `used[i] = false` and removing `nums[i]` from the permutation.

# Solutions
### CSharp

```csharp
public class Solution {
    private List < IList < int >> ans = new List < IList < int >> ();
    private List < int > t = new List < int > ();
    private int[] nums;
    private bool[] vis;
    public IList < IList < int >> PermuteUnique(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        vis = new bool[n];
        this.nums = nums;
        dfs(0);
        return ans;
    }
    private void dfs(int i) {
        if (i == nums.Length) {
            ans.Add(new List < int > (t));
            return;
        }
        for (int j = 0; j < nums.Length; ++j) {
            if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) {
                continue;
            }
            vis[j] = true;
            t.Add(nums[j]);
            dfs(i + 1);
            t.RemoveAt(t.Count - 1);
            vis[j] = false;
        }
    }
}
```

### Java

```java
class Solution { private List < List < Integer >> ans = new ArrayList <>(); private List < Integer > t = new ArrayList <>(); private int [] nums ; private boolean [] vis ; public List < List < Integer >> permuteUnique ( int [] nums ) { Arrays . sort ( nums ); this . nums = nums ; vis = new boolean [ nums . length ]; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i == nums . length ) { ans . add ( new ArrayList <>( t )); return ; } for ( int j = 0 ; j < nums . length ; ++ j ) { if ( vis [ j ] || ( j > 0 && nums [ j ] == nums [ j - 1 ] && ! vis [ j - 1 ])) { continue ; } t . add ( nums [ j ]); vis [ j ] = true ; dfs ( i + 1 ); vis [ j ] = false ; t . remove ( t . size () - 1 ); } } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[][]} */ var permuteUnique =
  function (nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const ans = [];
    const t = Array(n);
    const vis = Array(n).fill(false);
    const dfs = (i) => {
      if (i === n) {
        ans.push(t.slice());
        return;
      }
      for (let j = 0; j < n; ++j) {
        if (vis[j] || (j > 0 && nums[j] === nums[j - 1] && !vis[j - 1])) {
          continue;
        }
        t[i] = nums[j];
        vis[j] = true;
        dfs(i + 1);
        vis[j] = false;
      }
    };
    dfs(0);
    return ans;
  };

```

### CPP

```cpp
class Solution { public: vector < vector < int >> permuteUnique ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int n = nums . size (); vector < vector < int >> ans ; vector < int > t ( n ); vector < bool > vis ( n ); function < void ( int ) > dfs = [ & ]( int i ) { if ( i == n ) { ans . emplace_back ( t ); return ; } for ( int j = 0 ; j < n ; ++ j ) { if ( vis [ j ] || ( j && nums [ j ] == nums [ j - 1 ] && ! vis [ j - 1 ])) { continue ; } t [ i ] = nums [ j ]; vis [ j ] = true ; dfs ( i + 1 ); vis [ j ] = false ; } }; dfs ( 0 ); return ans ; } };
```

### Python

```python
from typing import List class Solution : # iterative, if new_perm not in new_res def permuteUnique ( self , nums : List [ int ]) -> List [ List [ int ]]: res = [[]] if nums is None or len ( nums ) == 0 : return res for num in nums : new_res = [] for perm in res : for i in range ( len ( perm ) + 1 ): new_perm = perm [: i ] + [ num ] + perm [ i :] if new_perm not in new_res : # Check for uniqueness new_res . append ( new_perm ) res = new_res return res ############## class Solution : # iterative def permuteUnique ( self , nums : List [ int ]) -> List [ List [ int ]]: nums . sort () # sort the input to handle duplicates res = [[]] for num in nums : new_res = [] for perm in res : for i in range ( len ( perm ) + 1 ): if i > 0 and perm [ i - 1 ] == num : # added for lc-47, as explained above "Why the Condition Works" break # skip duplicate new_perm = perm [: i ] + [ num ] + perm [ i :] # or perm.insert(index, num), like in lc-46 new_res . append ( new_perm ) res = new_res return res ############ class Solution : # dfs def permuteUnique ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( i : int ): if i == n : ans . append ( t [:]) return for j in range ( n ): if vis [ j ] or ( j and nums [ j ] == nums [ j - 1 ] and not vis [ j - 1 ]): continue t [ i ] = nums [ j ] vis [ j ] = True dfs ( i + 1 ) vis [ j ] = False n = len ( nums ) nums . sort () ans = [] t = [ 0 ] * n vis = [ False ] * n dfs ( 0 ) return ans
```