Generate All Permutations — Used Array, In-place Swap, and the Duplicate Skip Rule

Problem Statement#

Given an array nums, return all possible permutations. LeetCode 46 has distinct integers; LeetCode 47 (Permutations II) allows duplicates and must return only unique orderings.

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10
• All integers unique for LC 46; possibly duplicate for LC 47

Input:  nums = [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input:  nums = [1, 1, 2]   (LC 47)
Output: [[1,1,2],[1,2,1],[2,1,1]]

Why This Problem Matters#

Permutations is the canonical backtracking problem where order matters. The distinction between "every ordering" and "every selection" is foundational and shows up in scheduling, cryptographic key generation, and game-tree search. Amazon and Microsoft routinely ask LC 46 in phone screens to verify a candidate can implement choose-explore-unchoose without bugs.

Permutations II layers on the trickiest deduplication condition in all of backtracking: not used[i-1]. Many candidates either get the direction wrong or cannot explain why it works. Being able to derive the condition on the spot — not just memorize it — is exactly what separates an offer from a polite rejection at top-tier companies.

The in-place swap variant tests a different muscle. Reasoning about the array state, knowing that the unchoose step requires another swap, and understanding why generated order is no longer lexicographic — these are all signals an interviewer reads during system design conversations later in the loop.

The Core Insight#

For permutations, every position in the output sequence can hold any element that has not been placed yet. Unlike subsets, you do not move forward through the input — you re-scan it at every level and skip elements already used.

The used-array approach maintains a boolean array used. At each call you iterate from i = 0, skip used elements, mark, recurse, and unmark. Recursion depth is exactly n.

The in-place swap approach treats the slice nums[start:] as the available pool. You swap nums[start] with nums[i] to place element i at the current slot, recurse with start+1, and swap back. This avoids the used array but no longer produces lexicographic output.

For duplicates, after sorting, the condition is: skip nums[i] if i > 0, nums[i] == nums[i-1], and not used[i-1]. The logic: if the previous equal value was not used in this branch, a sibling branch already started with that value and explored the same subtree. If used[i-1] is true the previous element is an ancestor in the current branch — a genuinely different arrangement that must be allowed.

Visual Dry Run#

Input nums = [1, 2, 3] with the used-array approach:

Tree continues for 2 and 3 as roots, producing all 6 permutations.

For nums = [1, 1, 2] after sorting, when path=[] and i=1, we see nums[1]==nums[0] and used[0]=False, so we skip — the i=0 branch already explored everything starting with 1.

Solution (Optimal)#

class Solution:
    def permute(self, nums):
        result = []
        used = [False] * len(nums)
 
        def bt(current):
            if len(current) == len(nums):
                result.append(current[:])  # snapshot
                return
 
            for i in range(len(nums)):
                if used[i]:
                    continue                # already placed in this branch
                used[i] = True              # CHOOSE
                current.append(nums[i])
                bt(current)                 # EXPLORE
                current.pop()               # UNCHOOSE
                used[i] = False
 
        bt([])
        return result
 
    def permuteUnique(self, nums):
        nums.sort()                          # required for duplicate-skip
        result = []
        used = [False] * len(nums)
 
        def bt(current):
            if len(current) == len(nums):
                result.append(current[:])
                return
 
            for i in range(len(nums)):
                if used[i]:
                    continue
                # Skip if previous equal value was NOT used in this branch
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue
                used[i] = True
                current.append(nums[i])
                bt(current)
                current.pop()
                used[i] = False
 
        bt([])
        return result

var permute = function(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);
 
    const bt = (current) => {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;            // CHOOSE
            current.push(nums[i]);
            bt(current);               // EXPLORE
            current.pop();             // UNCHOOSE
            used[i] = false;
        }
    };
 
    bt([]);
    return result;
};
 
var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    const used = new Array(nums.length).fill(false);
 
    const bt = (current) => {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // Sibling already covered this starting value
            if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            current.push(nums[i]);
            bt(current);
            current.pop();
            used[i] = false;
        }
    };
 
    bt([]);
    return result;
};

Time: O(n! * n). There are n! leaves and copying each result takes O(n). Pruning in LC 47 reduces the constant factor. Space: O(n) for the recursion stack and used array, plus O(n! * n) for output.

Common Mistakes#

• Flipping the duplicate-skip condition to used[i-1] is True — this skips legitimate ancestor cases and produces duplicates
• Forgetting used[i] = False after recursion — subsequent siblings see the element as still placed
• Using a start index instead of a used array — works for subsets but breaks permutations
• Forgetting to sort before applying the duplicate-skip rule
• Recording at every node instead of only at leaves — only full-length sequences are valid permutations
• In the swap variant, forgetting the second swap that restores the array state

Interview Tips#

• Mention both the used-array and in-place swap variants and explain the trade-off
• For LC 47, state the duplicate-skip condition out loud and walk through one branch where it fires
• Use n=3 or n=4 for the walkthrough — small enough to enumerate, big enough to show the structure
• Note that n! grows fast (8! = 40320) so input sizes are small; emphasize the snapshot O(n) copy
• Mention LC 31 (Next Permutation) as a related O(n) in-place trick that does not need backtracking

Follow-up Questions#

• How does the in-place swap variant work? Hint: swap nums[start] with nums[i], recurse with start+1, swap back.
• How do you generate the next permutation lexicographically? Hint: LeetCode 31, find first descending suffix.
• How many unique permutations does [1,1,2,2,3] have? Hint: 5! / (2! * 2! * 1!) = 30.
• What if a permutation must satisfy an adjacency constraint? Hint: LC 526 Beautiful Arrangement, validity check inside the loop.
• How do you find the k-th permutation directly? Hint: LC 60, factorial-base decoding without enumeration.

Key Takeaways#

• Permutations uses a used array because every element is a candidate at every position
• Record only at leaves where len(current) == len(nums)
• The duplicate-skip rule is not used[i-1] after sorting — counterintuitive but correct
• Always snapshot with current[:] or [...current] to avoid reference bugs
• The in-place swap variant trades a different output order for less auxiliary space
• Recursion depth is exactly n, branching factor up to n; total work O(n! * n)
• Understanding why not used[i-1] works is a stronger signal than memorizing it