Permutations II

The most straightforward way to handle duplicates is to not handle them at all during generation — instead, generate every possible permutation (including duplicates) and then remove the duplicates afterward.

Think of it like writing down every possible arrangement of cards, even if some cards have the same face value. Once you have the full list, you go through it and cross out any arrangement you have already seen. The surviving entries are your unique permutations.

To generate all permutations, we use a basic recursive approach: for each position in the result, try placing every unused element there, then recurse for the remaining positions. Since there are n! total arrangements (before deduplication), and we store them in a set that automatically removes duplicates, the final output contains only unique permutations.

This approach is simple but wasteful — it generates duplicate permutations only to throw them away. For an input like [1, 1, 1, 1, 1, 2, 2, 2], there would be far more duplicate work than useful work.

Let's trace through with nums = [1, 1, 2]:

Step 1: We generate all 3! = 6 permutations using a standard backtracking approach with a visited array. The visited array tracks which indices are currently used.

Step 2: Position 0 — try index 0 (value 1). Mark visited[0] = true. Recurse for position 1.

Step 3: Position 1 — try index 1 (value 1). Mark visited[1] = true. Recurse for position 2.

Step 4: Position 2 — try index 2 (value 2). Mark visited[2] = true. All positions filled → permutation [1, 1, 2]. Add to set.

Step 5: Backtrack position 2. Backtrack position 1. Try index 2 (value 2) at position 1. Mark visited[2] = true.

Step 6: Position 2 — try index 1 (value 1). Permutation [1, 2, 1]. Add to set.

Step 7: Backtrack all. Now try index 1 (value 1) at position 0.

Step 8: Position 1 — try index 0 (value 1). Permutation eventually becomes [1, 1, 2]. Set already contains this → duplicate detected!

Step 9: Continue generating: [1, 2, 1] → duplicate. [2, 1, 1] → new! Add to set.

Step 10: After all 6 permutations: [1,1,2], [1,2,1], [1,1,2], [1,2,1], [2,1,1], [2,1,1]. The set keeps only unique ones: {[1,1,2], [1,2,1], [2,1,1]}.

Result: [[1,1,2], [1,2,1], [2,1,1]]. We generated 6 permutations but only 3 were unique — 50% of the work was wasted.

1. Create a visited array of size n, initialized to false.
2. Use a set (or hash set of tuples) to store unique permutations.
3. Define a recursive function generate(pos, perm):
   a. If pos == n, convert perm to a tuple and add to the set.
   b. For each index j from 0 to n-1:
   • If visited[j] is false, mark it true, place nums[j] at perm[pos], recurse with pos+1, then unmark.
4. Start with generate(0, empty_perm).
5. Convert the set back to a list of lists and return.

Time Complexity: O(n! × n)

The algorithm generates all n! permutations regardless of duplicates. For each permutation, inserting it into a set costs O(n) for comparison/hashing. Total: O(n! × n). When there are many duplicates, a large fraction of this work produces permutations that are immediately discarded.

Space Complexity: O(n! × n)

The set stores up to n!/∏(count_i!) unique permutations, each of size n. In the worst case (all distinct elements), this is O(n! × n). The recursion stack uses O(n) space, and the visited array uses O(n).

An alternative strategy avoids using a global set by preventing duplicates at each level of recursion using a local set.

The idea is based on swapping: to generate all permutations of an array, we fix each position one at a time. For position i, we try swapping element at index i with each element at indices i through n-1. After the swap, we recurse to fill position i+1 through n-1, then swap back (backtrack).

The duplicate-avoidance trick is simple: at each recursion level, we maintain a local set of values we have already placed at position i. Before performing a swap, we check if that value has already been tried at this position. If yes, we skip it.

Think of it like assigning seats. For the first seat, you try each person once. If two people are identical (same value), placing either one in seat 1 gives the same arrangement for the rest — so you only place that value once per seat.

This approach does not require pre-sorting. The local set at each level ensures that no value appears at the same position twice across different recursive branches.

Let's trace through with nums = [1, 1, 2]:

Step 1: At position 0, our local set is empty. Try swapping index 0 with index 0 (no-op). Value at position 0 is 1. Add 1 to local set = {1}. Recurse for position 1.

Step 2: At position 1, local set = {}. Swap index 1 with index 1 (no-op). Value = 1. Add 1 to local set = {1}. Recurse for position 2.

Step 3: At position 2, only index 2 left. Permutation = [1, 1, 2]. Record it. Backtrack.

Step 4: Back at position 1. Swap index 1 with index 2. Array becomes [1, 2, 1]. Value at position 1 is now 2. Local set = {1} → 2 not in set → add. Local set = {1, 2}. Recurse.

Step 5: Permutation = [1, 2, 1]. Record it. Swap back: array returns to [1, 1, 2]. Backtrack to position 0.

Step 6: At position 0, try swapping index 0 with index 1. Value at index 1 is 1. Local set = {1} → 1 is ALREADY in set. SKIP! This prevents regenerating permutations that start with 1, which we already fully explored.

Step 7: Try swapping index 0 with index 2. Array becomes [2, 1, 1]. Value = 2. Add 2 to local set = {1, 2}. Recurse for position 1.

Step 8: At position 1, local set = {}. Swap 1 with 1 (no-op) → value 1. Add to set. Recurse.

Step 9: Permutation = [2, 1, 1]. Record it. Backtrack.

Step 10: At position 1, swap index 1 with index 2. Value = 1. Local set = {1} → 1 ALREADY in set. SKIP! No more swaps. Backtrack.

Step 11: Swap back: array returns to [1, 1, 2]. Done.

Result: [[1,1,2], [1,2,1], [2,1,1]]. Exactly 3 permutations generated with zero duplicates. The local set prevented 2 unnecessary branches.

1. Define a recursive function permute(pos) to fill positions from pos to n-1.
2. Base case: If pos == n, add the current array state as a permutation to results.
3. Create a local set seen for the current recursion level.
4. For each index j from pos to n-1:
   a. If nums[j] is already in seen, skip (duplicate value at this position).
   b. Add nums[j] to seen.
   c. Swap nums[pos] with nums[j].
   d. Recurse with permute(pos + 1).
   e. Swap back nums[pos] with nums[j] (backtrack).
5. Start with permute(0).
6. Return collected results.

Time Complexity: O(n! / ∏(count_i!) × n)

The algorithm generates only unique permutations. If there are c_1 copies of value v1, c_2 copies of value v2, etc., the number of unique permutations is n! / (c_1! × c_2! × ...). For each permutation, copying it takes O(n). The local set checks at each level cost O(1) per check on average (hash set).

Space Complexity: O(n × n)

The recursion stack depth is O(n). At each recursion level, a local set of up to O(n) values is created. In the worst case, there are n levels each with a set of up to n elements, giving O(n²) for the sets. However, this is often much smaller in practice. Excluding output, auxiliary space is O(n²) worst case.

The optimal approach combines sorting with backtracking and a single elegant rule to skip duplicates.

First, we sort the array so that duplicate values are grouped together. Then, we build permutations position by position. For each position, we try placing each unused element there. The key insight is a one-line duplicate-skipping rule:

If the current element nums[j] equals the previous element nums[j-1], AND nums[j-1] has NOT been used in the current permutation (i.e., visited[j-1] is false), then skip nums[j].

Why does this work? Consider nums = [1, 1, 2] (sorted). When we are filling a position and encounter the second 1 (index 1), we check: has the first 1 (index 0) already been placed in the current permutation? If NOT, that means the first 1 is still available but we are choosing the second 1 before it. This would create the exact same sub-problem as using the first 1 — a duplicate branch. So we skip it.

This enforces a rule: among duplicate values, always use the earlier occurrence first. This ensures each unique permutation is generated exactly once.

Think of it like numbering identical items. If you have two red marbles, you label them Red#1 and Red#2. The rule says: you can only use Red#2 in a permutation if Red#1 is already used somewhere earlier. This prevents identical arrangements from being generated through different orderings of the same marbles.

Let's trace through with nums = [1, 1, 2] (already sorted):

Step 1: Initialize: visited = [F, F, F], perm = [_, _, _]. Fill position 0.

Step 2: Try j=0 (nums[0]=1). Not visited. No previous element to compare. Place 1 at perm[0]. visited = [T, F, F]. Recurse for position 1.

Step 3: Try j=0: visited → skip. Try j=1 (nums[1]=1). Not visited. Check duplicate rule: nums[1]==nums[0] and visited[0]==T (first 1 IS used). Condition not visited[0] is false → do NOT skip. Place 1 at perm[1]. visited = [T, T, F].

Step 4: Position 2: j=0 visited, j=1 visited. Try j=2 (nums[2]=2). Place 2 at perm[2]. Permutation [1, 1, 2]. Record it.

Step 5: Backtrack to position 1. Unmark j=1. Try j=2 (nums[2]=2). Not visited. Place 2 at perm[1]. visited = [T, F, T]. Recurse.

Step 6: Position 2: j=0 visited. Try j=1 (nums[1]=1). Place 1 at perm[2]. Permutation [1, 2, 1]. Record it.

Step 7: Backtrack to position 0. Unmark j=0. Try j=1 (nums[1]=1). Check duplicate rule: nums[1]==nums[0] and visited[0]==F. Condition not visited[0] is TRUE → SKIP! The first 1 is unused, so using the second 1 first would create a duplicate.

Step 8: Try j=2 (nums[2]=2). Not visited, no duplicate. Place 2 at perm[0]. visited = [F, F, T]. Recurse.

Step 9: Position 1: Try j=0 (nums[0]=1). Place 1 at perm[1]. visited = [T, F, T]. Recurse.

Step 10: Position 2: Try j=1 (nums[1]=1). Check: nums[1]==nums[0] and visited[0]==T → do not skip. Place 1 at perm[2]. Permutation [2, 1, 1]. Record it.

Step 11: Backtrack to position 1. Try j=1 (nums[1]=1). Check: nums[1]==nums[0] and visited[0]==F → SKIP! (first 1 not used yet).

Result: [[1,1,2], [1,2,1], [2,1,1]]. Exactly 3 unique permutations, with duplicates pruned at the source via a simple boolean check.

1. Sort the input array nums. This groups duplicate values together.
2. Create a visited boolean array of size n, all initialized to false.
3. Create a perm array of size n to hold the current permutation being built.
4. Define a recursive function backtrack(pos):
   a. Base case: If pos == n, add a copy of perm to the result.
   b. For each index j from 0 to n-1:
   • If visited[j] is true, skip (already used in current permutation).
   • If j > 0 AND nums[j] == nums[j-1] AND visited[j-1] is false, skip (duplicate pruning).
   • Otherwise: set perm[pos] = nums[j], mark visited[j] = true, recurse with backtrack(pos + 1), then set visited[j] = false (backtrack).
5. Start with backtrack(0).
6. Return the collected results.

Time Complexity: O(n × n!/(c_1! × c_2! × ... × c_m!))

Where c_i is the count of the i-th distinct value. The algorithm generates exactly n!/(c_1! × c_2! × ... × c_m!) unique permutations — no duplicates. For each permutation, copying it takes O(n). The sorting step takes O(n log n) which is dominated by the permutation generation. At each recursion level, we iterate through at most n candidates, but the pruning ensures we only explore branches that lead to unique results.

In the worst case (all elements distinct), this becomes O(n × n!). In the best case (all elements identical), this produces only 1 permutation in O(n) time.

Space Complexity: O(n)

The recursion stack depth is O(n) since each level fills one position. The visited array is O(n) and the perm array is O(n). No sets or hash maps are needed. Excluding output, total auxiliary space is O(n). This is more space-efficient than the swap-based approach which needs O(n²) for per-level sets.