Permutations (LC 46) — Backtracking with Visited Array and Swap Approach [Microsoft / LinkedIn]

Problem Statement#

Given an array nums of distinct integers, return all possible permutations. You may return the answer in any order.

Example 1:

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

Example 2:

Input:  nums = [0, 1]
Output: [[0,1],[1,0]]

Example 3:

Input:  nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All integers in nums are unique

Why This Problem Matters#

LC 46 — Permutations is one of the most important problems in the entire backtracking category. It appears in interviews at Microsoft, LinkedIn, Amazon, and Google, not because generating permutations is a common engineering task, but because the problem is a perfect filter for whether a candidate truly understands recursive state management.

The reason interviewers love this problem is that it has exactly two failure modes that reveal incomplete understanding. The first failure mode is candidates who know the output is n! permutations but cannot write a correct recursive function that avoids duplicating or skipping elements. The second failure mode is candidates who write a correct function but cannot explain why backtracking is necessary — specifically, why you must undo your changes after each recursive call returns. Both failure modes are visible in the first five minutes of live coding.

Beyond the interview room, the permutation problem is the foundation for a family of harder backtracking problems: combinations, subsets, N-queens, Sudoku solver, word search, and the k-th permutation (LC 60). Every one of those problems uses the same backtracking template — build a candidate solution incrementally, recurse when valid, undo when returning. Understanding permutations deeply means you can derive the solution to all of those problems from scratch under pressure.

The problem also has a direct real-world analog: test case generation, job scheduling where all orderings must be evaluated, and combinatorial optimization. The backtracking insight transfers.

The Backtracking Insight#

The central question in generating permutations is: at each position in the output array, which numbers are still available to place?

For nums = [1, 2, 3], position 0 can take any of the three numbers. Once you commit a number to position 0, position 1 can take either of the two remaining numbers. Position 2 is forced — only one number remains. This hierarchical narrowing of choices is exactly what recursion models.

Backtracking is the mechanism that lets you reuse a single data structure across all recursive branches. After you explore all permutations that begin with 1, you need to make 1 available again so that 2 and 3 can appear at position 0. This "undo the choice before returning" is the backtrack step.

Approach 1 — Visited Array#

The clearest implementation uses a boolean visited array (sometimes called used). The idea:

1. Maintain a current list that holds the permutation being built.
2. Maintain a visited array of the same length as nums, initialized to all False.
3. At each recursive call, loop over all indices. If visited[i] is False, that element is available. Mark it True, append nums[i] to current, and recurse.
4. When recursion returns, undo: pop the last element from current and set visited[i] back to False.
5. Base case: when len(current) == len(nums), a complete permutation has been built — copy it into the result.

The visited array guarantees that each element appears exactly once per permutation, without mutating the original nums array. This approach is slightly more code but extremely readable and easy to explain to an interviewer.

Approach 2 — In-Place Swap#

The swap approach avoids the extra visited array entirely by treating the array itself as two logical regions:

• Positions 0 through start - 1: already fixed for this branch of recursion.
• Positions start through n - 1: still available to be placed at position start.

At each call, iterate i from start to n - 1. Swap nums[start] with nums[i] (bringing element i into the fixed region), recurse with start + 1, then swap back to restore the array. When start == n, all positions are fixed — record the current array.

This approach uses O(1) extra space beyond the recursion stack and is slightly more concise. The trade-off is that the swap-based traversal does not enumerate permutations in lexicographic order, which matters for some follow-ups.

Visual Dry Run#

Let us trace the swap approach for nums = [1, 2, 3] step by step. Each node shows the array state and which index start is being processed.

Initial: [1, 2, 3],  start = 0
 
Fix index 0 = 1  (swap 0↔0, no change)
  [1, 2, 3],  start = 1
    Fix index 1 = 2  (swap 1↔1, no change)
      [1, 2, 3],  start = 2
        Fix index 2 = 3  (swap 2↔2, no change)
          start == 3 → record [1, 2, 3]  ✓
        swap back 2↔2  (no change)
    swap back 1↔1  (no change)
 
    Fix index 1 = 3  (swap 1↔2 → [1, 3, 2])
      [1, 3, 2],  start = 2
        Fix index 2 = 2  (swap 2↔2, no change)
          start == 3 → record [1, 3, 2]  ✓
        swap back 2↔2
    swap back 1↔2  → restore [1, 2, 3]
 
Fix index 0 = 2  (swap 0↔1 → [2, 1, 3])
  [2, 1, 3],  start = 1
    Fix index 1 = 1  (swap 1↔1, no change)
      [2, 1, 3],  start = 2
          start == 3 → record [2, 1, 3]  ✓
    Fix index 1 = 3  (swap 1↔2 → [2, 3, 1])
      [2, 3, 1],  start = 2
          start == 3 → record [2, 3, 1]  ✓
    swap back 0↔1  → restore [1, 2, 3]  (wait — see note below)
 
Fix index 0 = 3  (swap 0↔2 → [3, 2, 1])
  [3, 2, 1],  start = 1
    Fix index 1 = 2  (swap 1↔1, no change)
      [3, 2, 1],  start = 2
          start == 3 → record [3, 2, 1]  ✓
    Fix index 1 = 1  (swap 1↔2 → [3, 1, 2])
      [3, 1, 2],  start = 2
          start == 3 → record [3, 1, 2]  ✓
    swap back 0↔2  → restore [1, 2, 3]
 
Final result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]]
Total: 3! = 6 permutations  ✓

The key observation: every time the recursion returns from dfs(start + 1), the swap back restores the array to exactly the state it was in before the swap. This is the backtrack. Without it, subsequent loop iterations would operate on a corrupted array.

Now let us trace the visited-array approach for the same input to show how it differs:

current = [],  visited = [F, F, F]
 
  try i=0 (nums[0]=1): current=[1], visited=[T,F,F]
    try i=1 (nums[1]=2): current=[1,2], visited=[T,T,F]
      try i=2 (nums[2]=3): current=[1,2,3], visited=[T,T,T]
        len==3 → record [1,2,3]  ✓
      backtrack: current=[1,2], visited=[T,T,F]
    try i=2 (nums[2]=3): current=[1,3], visited=[T,F,T]
      try i=1 (nums[1]=2): current=[1,3,2], visited=[T,T,T]
        len==3 → record [1,3,2]  ✓
      backtrack: current=[1], visited=[T,F,F]
  backtrack: current=[], visited=[F,F,F]
 
  try i=1 (nums[1]=2): current=[2], visited=[F,T,F]
    ...  (produces [2,1,3] and [2,3,1])
 
  try i=2 (nums[2]=3): current=[3], visited=[F,F,T]
    ...  (produces [3,1,2] and [3,2,1])

The visited approach always enumerates in the original element order at each level, which produces lexicographic output when nums is sorted. The swap approach does not guarantee this but uses O(1) extra space.

Common Mistakes#

Mistake 1 — Appending the Reference Instead of a Copy#

In Python, res.append(current) appends a reference to the current list, not a snapshot of it. Because current is mutated throughout the recursion, every entry in res will point to the same list — which at the end of recursion will be empty. The fix is always res.append(current[:]) or res.append(list(current)).

In JavaScript, res.push(nums) has the same problem when using the swap approach. The fix is res.push([...nums]).

This mistake produces an output like [[], [], [], [], [], []] — six empty lists — which is immediately obvious but the root cause is not always clear to beginners under pressure.

Mistake 2 — Forgetting to Swap Back (Missing the Backtrack)#

Writing dfs(start + 1) without the subsequent swap back means the array is permanently modified after the first branch of the loop. Every subsequent iteration of the outer for loop will see a scrambled array rather than the original. The output will be wrong in subtle ways — some permutations will be duplicated, others missing entirely.

This is the single most common mistake on this problem in live coding sessions. The fix is to always pair every swap before the recursive call with an identical swap after it returns.

Mistake 3 — Using a Set to Track Visited Elements#

A natural but incorrect instinct is to track which values have been used, rather than which indices. Code like if nums[i] not in used_set is wrong when the input contains repeated values (relevant for LC 47) and also does not correctly model the problem structure. Index-based tracking with a boolean array is always correct and more general.

Even for LC 46 where all integers are distinct, using a value-based set instead of an index-based boolean array will fail on inputs like [-1, -1] if you ever generalize. Form the correct habit from the start.

Mistake 4 — Wrong Loop Range in the Swap Approach#

In the swap approach, the inner loop must start at start, not at 0. Starting from 0 would allow elements in the already-fixed region (indices before start) to be moved, which breaks the invariant. The loop is for i in range(start, len(nums)).

Solutions#

Python — Approach 1: Visited Array (Clearest for Interviews)#

def permute(nums: list[int]) -> list[list[int]]:
    n = len(nums)
    result = []        # will hold all complete permutations
    current = []       # permutation being built incrementally
    visited = [False] * n  # visited[i] is True if nums[i] is already in current
 
    def backtrack():
        # Base case: current holds a complete permutation of length n
        if len(current) == n:
            result.append(current[:])  # append a COPY, not a reference
            return
 
        for i in range(n):
            if visited[i]:
                # nums[i] is already used in the current permutation — skip
                continue
 
            # Choose nums[i] for the next position
            visited[i] = True
            current.append(nums[i])
 
            # Recurse to fill the remaining positions
            backtrack()
 
            # Backtrack: undo the choice so we can try the next element
            current.pop()
            visited[i] = False
 
    backtrack()
    return result

Python — Approach 2: In-Place Swap (Space-Efficient)#

def permute(nums: list[int]) -> list[list[int]]:
    result = []
 
    def backtrack(start: int):
        # Base case: everything from index 0..start-1 is fixed
        # The entire array is one complete permutation
        if start == len(nums):
            result.append(nums[:])  # snapshot the current state
            return
 
        for i in range(start, len(nums)):
            # Bring nums[i] into the "fixed" region by swapping with nums[start]
            nums[start], nums[i] = nums[i], nums[start]
 
            # Recurse: fix the next position (start+1)
            backtrack(start + 1)
 
            # Backtrack: restore the array to its state before this swap
            # so the next iteration of the loop sees the original arrangement
            nums[start], nums[i] = nums[i], nums[start]
 
    backtrack(0)
    return result

JavaScript — Approach 1: Visited Array#

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const n = nums.length;
    const result = [];      // accumulates all complete permutations
    const current = [];     // the permutation being built
    const visited = new Array(n).fill(false); // visited[i] = nums[i] used?
 
    function backtrack() {
        // Base case: current is a complete permutation
        if (current.length === n) {
            result.push([...current]); // spread creates a shallow copy
            return;
        }
 
        for (let i = 0; i < n; i++) {
            if (visited[i]) continue; // skip elements already in current
 
            // Make the choice: add nums[i] to the current permutation
            visited[i] = true;
            current.push(nums[i]);
 
            // Recurse to fill the next position
            backtrack();
 
            // Undo the choice (backtrack)
            current.pop();
            visited[i] = false;
        }
    }
 
    backtrack();
    return result;
};

JavaScript — Approach 2: In-Place Swap#

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = [];
 
    function backtrack(start) {
        // Base case: all positions from 0..start-1 are fixed
        if (start === nums.length) {
            result.push([...nums]); // MUST spread — not push(nums)
            return;
        }
 
        for (let i = start; i < nums.length; i++) {
            // Swap: bring nums[i] to position "start"
            [nums[start], nums[i]] = [nums[i], nums[start]];
 
            // Recurse with start+1 to fix the next position
            backtrack(start + 1);
 
            // Swap back to restore the array for the next loop iteration
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }
 
    backtrack(0);
    return result;
};

Complexity Analysis#

Time complexity breakdown: There are n! permutations. Recording each one requires copying an array of length n, which costs O(n). The total work is therefore O(n! x n). The traversal of the recursion tree itself is also O(n! x n) — each of the n! leaves is reached through a path of length n.

Space complexity: Both approaches use O(n) recursion stack depth (the maximum depth equals n). The visited-array approach additionally uses O(n) for the visited and current arrays, so its extra space is O(n). The swap approach uses O(1) extra space beyond the stack. In practice the distinction rarely matters for n <= 6, but interviewers appreciate the analysis.

Output space: Both approaches produce n! permutations each of length n, so the output itself takes O(n! x n) space regardless of which approach you use. This is unavoidable — you cannot do better than the size of what you must return.

Follow-up Questions#

LC 47 — Permutations II (Array with Duplicates)#

If the input can contain duplicates — for example nums = [1, 1, 2] — the basic algorithm produces duplicate permutations. LC 47 asks you to return only unique permutations.

The standard fix using the visited-array approach:

1. Sort nums first. This brings duplicates adjacent to each other.
2. Add a pruning condition: if i > 0 and nums[i] == nums[i-1] and not visited[i-1], skip i. This prevents choosing the second copy of a duplicate before the first copy has been placed, which is what generates the duplicates.

The key insight: not visited[i-1] means the previous identical element was already backtracked — if we were to choose nums[i] now (without nums[i-1] being in the current permutation), we would generate the same permutation we generated when we chose nums[i-1] first. Skipping this case eliminates all duplicates.

# LC 47 — Permutations II
def permuteUnique(nums: list[int]) -> list[list[int]]:
    nums.sort()   # sort to bring duplicates adjacent
    n = len(nums)
    result = []
    current = []
    visited = [False] * n
 
    def backtrack():
        if len(current) == n:
            result.append(current[:])
            return
 
        for i in range(n):
            if visited[i]:
                continue
            # Skip duplicate: same value as previous AND previous was backtracked
            if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
                continue
 
            visited[i] = True
            current.append(nums[i])
            backtrack()
            current.pop()
            visited[i] = False
 
    backtrack()
    return result

LC 60 — Permutation Sequence (k-th Permutation)#

LC 60 asks: given n and k, return the k-th permutation of [1, 2, ..., n] in lexicographic order. Generating all permutations and indexing into the result is too slow for large n.

The optimal approach uses factorial number system decomposition. The first element of the k-th permutation can be determined by dividing (k-1) by (n-1)!. The quotient tells you which element (by index into the remaining sorted list) goes in position 0. Subtract and repeat for each subsequent position.

This runs in O(n^2) time with no recursion, compared to O(n! x n) for the generate-all approach. In an interview, mentioning this optimization — even without implementing it fully — demonstrates strong mathematical reasoning and awareness of when backtracking is overkill.

This Pattern Solves#

The backtracking template from LC 46 applies directly to a wide family of problems. Recognizing which problem belongs to this family is half the battle:

• LC 47 — Permutations II: Same template plus sort and a duplicate-skip condition.
• LC 77 — Combinations: Choose k elements from n; same template but start index advances each recursion level to avoid reuse and prevent ordering duplicates.
• LC 78 — Subsets: Record the current state at every recursion level, not just the leaves.
• LC 39 — Combination Sum: Elements can be reused; do not advance the start index after choosing.
• LC 51 — N-Queens: Same choose-recurse-unchoose loop, with a more complex validity check before recursing.
• LC 79 — Word Search: Same template applied to a 2-D grid; visited becomes a 2-D boolean grid.
• LC 37 — Sudoku Solver: Same template; the "choice" is which digit to place in an empty cell.

In all of these, the template is identical:

for each valid choice:
    make the choice
    recurse
    undo the choice

The only thing that changes between problems is what "valid" means and when the base case fires.

Key Takeaways#

• LeetCode 46 — Permutations is a Medium asked at Microsoft, LinkedIn, and Amazon; it teaches backtracking as disciplined exhaustive search.
• Always copy at the base case: result.append(current[:]) not result.append(current) — appending the live list records a reference that will be mutated later.
• Always restore state after recursion (backtrack step): mark element as unvisited or swap back — this is what makes the algorithm correct, not optional cleanup.
• Visited-array approach: track which indices are used; time O(n * n!), space O(n) for the visited array plus recursion stack.
• Swap approach: swap element to current position, recurse, swap back — avoids the extra visited array but harder to reason about.
• Total permutations: n! — the algorithm generates exactly n! leaf nodes, one per unique permutation.
• Escalates to LC 47 (Permutations II with duplicates): sort first, then skip nums[i] == nums[i-1] when visited[i-1] is false — same backtracking skeleton.

Start with the visited-array approach in interviews — it is more lines of code but the state is explicit and easy to reason about under pressure. Mention the swap approach as the space-optimized variant. Show you know both.