Problem Description

You are given an array nums containing distinct integers. Your task is to generate all possible permutations of these integers.

A permutation is a rearrangement of all elements where order matters. For example, if nums = [1, 2, 3], the permutations would be [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

The key points to understand:

• The input array contains distinct integers (no duplicates)
• You need to return all possible permutations
• Each permutation should use all elements from the original array exactly once
• The permutations can be returned in any order

For an array of length n, there will be exactly n! (n factorial) permutations in the result.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem doesn't involve nodes and edges or graph traversal. We're working with an array of integers and need to generate permutations.

Need to solve for kth smallest/largest?

• No: We're not looking for a specific kth element. We need to generate all possible permutations.

Involves Linked Lists?

• No: The input is an array, not a linked list structure.

Does the problem have small constraints?

• Yes: Generating permutations has factorial time complexity O(n!), which grows extremely fast. This problem is typically given with small constraints (usually n ≤ 10 or similar) because for n=10, we already have 3,628,800 permutations. The exponential nature of permutations makes this feasible only for small inputs.

Brute force / Backtracking?

• Yes: This is the perfect fit! We need to:
  • Systematically explore all possible arrangements
  • Build permutations one element at a time
  • Track which elements have been used
  • Backtrack when we've completed a permutation to explore other possibilities

Conclusion: The flowchart correctly leads us to the Backtracking approach. This makes sense because:

1. We need to explore all possible combinations exhaustively
2. We build solutions incrementally (position by position)
3. We need to undo choices (backtrack) to explore alternative paths
4. The constraint size is small enough to handle the exponential complexity

Intuition

When we need to generate all permutations, think about how you would do it manually. If you had cards numbered [1, 2, 3], you'd pick one card for the first position, then pick from the remaining cards for the second position, and so on.

The key insight is that we're making a series of choices:

• For the first position, we can choose any of the n numbers
• For the second position, we can choose any of the remaining n-1 numbers
• This continues until all positions are filled

This naturally suggests a recursive approach where we:

1. Try placing each available number at the current position
2. Mark that number as "used" so we don't pick it again
3. Recursively fill the next position
4. When we've filled all positions, we've found one complete permutation
5. Backtrack by unmarking the number as "used" to explore other possibilities

The backtracking happens because after exploring all permutations that start with, say, 1 in the first position, we need to "undo" that choice and try 2 in the first position, then 3, and so on.

We use a boolean array vis (visited) to track which numbers have been used in the current permutation being built. The array t stores the current permutation being constructed. When i reaches n (all positions filled), we've successfully built a complete permutation and add it to our answer.

The beauty of this approach is that it systematically explores all n! possibilities by building them incrementally and backtracking when needed, ensuring we don't miss any permutation or generate duplicates.

Learn more about Backtracking patterns.

Solution Approach

The solution uses DFS (Depth-First Search) with backtracking to generate all permutations. Let's walk through the implementation:

Core Data Structures:

• vis: A boolean array of size n to track which numbers have been used in the current permutation
• t: A temporary array of size n to build each permutation
• ans: The result list to store all complete permutations

The DFS Function: The function dfs(i) represents that we've filled the first i positions and now need to fill position i.

Algorithm Steps:

1. Base Case: When i >= n, all positions are filled. We've completed a valid permutation, so we add a copy of t to our answer list.

2. Recursive Case: For position i, we try each number from the original array:

   • Enumerate through all numbers in nums with their indices
   • Check if number at index j is available (not vis[j])
   • If available:
     • Mark it as used: vis[j] = True
     • Place it at position i: t[i] = x
     • Recursively fill the next position: dfs(i + 1)
     • Backtrack: Unmark it as used: vis[j] = False

Why This Works:

• The vis array ensures each number is used exactly once in each permutation
• The backtracking (setting vis[j] = False) allows us to reuse numbers in different positions for other permutations
• Starting from position 0 and filling positions sequentially ensures we explore all possible arrangements systematically

Time Complexity: O(n × n!) - There are n! permutations, and each takes O(n) time to construct (copying the array when adding to results).

Space Complexity: O(n) for the recursion stack and auxiliary arrays (not counting the output).

Example Walkthrough

Let's trace through the algorithm with nums = [1, 2, 3] to see how it generates all 6 permutations.

Initial Setup:

• vis = [False, False, False] (no numbers used yet)
• t = [_, _, _] (empty permutation being built)
• ans = [] (no complete permutations yet)

Starting DFS(0) - Filling position 0:

1. Choose 1 for position 0:

   • Set vis[0] = True, t[0] = 1 → t = [1, _, _]
   • Call DFS(1) to fill position 1

   In DFS(1):

   • Choose 2 (index 1, not visited): vis[1] = True, t[1] = 2 → t = [1, 2, _]

   • Call DFS(2)

     In DFS(2):

     • Only 3 is available: vis[2] = True, t[2] = 3 → t = [1, 2, 3]
     • Call DFS(3)
     • Base case reached! Add [1, 2, 3] to ans
     • Backtrack: vis[2] = False

   • Back in DFS(1), try next number

   • Choose 3 (index 2, not visited): vis[2] = True, t[1] = 3 → t = [1, 3, _]

   • Call DFS(2)

     In DFS(2):

     • Only 2 is available: vis[1] = True, t[2] = 2 → t = [1, 3, 2]
     • Call DFS(3)
     • Base case reached! Add [1, 3, 2] to ans
     • Backtrack: vis[1] = False

   • Backtrack from DFS(1): vis[2] = False

   • Backtrack from DFS(0): vis[0] = False

2. Choose 2 for position 0:

   • Set vis[1] = True, t[0] = 2 → t = [2, _, _]
   • Call DFS(1)

   Following similar logic:

   • DFS(1) tries 1, then 3
   • This generates [2, 1, 3] and [2, 3, 1]
   • Backtrack: vis[1] = False

3. Choose 3 for position 0:

   • Set vis[2] = True, t[0] = 3 → t = [3, _, _]
   • Call DFS(1)

   Following similar logic:

   • DFS(1) tries 1, then 2
   • This generates [3, 1, 2] and [3, 2, 1]
   • Backtrack: vis[2] = False

Final Result: ans = [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

The key insight is how backtracking allows us to systematically explore all branches of the decision tree. After exploring all permutations starting with 1, we backtrack (unmark 1 as used) and try 2 at position 0, then 3. This ensures we generate all 3! = 6 permutations without duplicates.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n! × n)

The algorithm generates all permutations of the input array. For an array of size n, there are n! permutations. The DFS function explores each position in the permutation:

• At position 0, we have n choices
• At position 1, we have n-1 choices (one element is already used)
• At position 2, we have n-2 choices
• And so on...

This gives us n × (n-1) × (n-2) × ... × 1 = n! recursive calls. Additionally, when we reach a complete permutation (i >= n), we append a copy of the current permutation t[:] to the answer, which takes O(n) time. Since we do this for all n! permutations, the total time complexity is O(n! × n).

Space Complexity: O(n)

The space complexity consists of:

• The recursion stack depth: O(n) - the maximum depth is n when building a complete permutation
• The vis array: O(n) - tracking which elements are used
• The t array: O(n) - storing the current permutation being built
• The ans array stores all permutations: O(n! × n), but this is typically not counted as it's the required output

Excluding the output storage, the auxiliary space complexity is O(n) as the dominant factors are the recursion stack and the auxiliary arrays, all of which scale linearly with n.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Create a Copy When Adding to Results

The Pitfall: One of the most common mistakes is adding the reference to the current permutation array directly to the results instead of creating a copy:

# WRONG - adds reference to the same array
if index >= n:
    result.append(current_permutation)  # Bug!
    return

Why It's a Problem: Since we're reusing the same current_permutation array throughout the recursion, all entries in result would end up pointing to the same array object. The final result would contain multiple references to the same array in its last modified state.

The Solution: Always create a copy of the array when adding to results:

# CORRECT - creates a new list
if index >= n:
    result.append(current_permutation[:])  # Makes a copy
    # OR
    result.append(list(current_permutation))  # Also makes a copy
    return

2. Incorrect or Missing Backtracking

The Pitfall: Forgetting to reset the used flag after the recursive call:

# WRONG - missing backtrack
for j, num in enumerate(nums):
    if not used[j]:
        used[j] = True
        current_permutation[index] = num
        backtrack(index + 1)
        # Missing: used[j] = False

Why It's a Problem: Without resetting used[j] to False, once a number is used in the first permutation branch, it remains marked as used for all subsequent branches. This would result in generating only one permutation instead of all n! permutations.

The Solution: Always reset the state after the recursive call returns:

# CORRECT - proper backtracking
for j, num in enumerate(nums):
    if not used[j]:
        used[j] = True
        current_permutation[index] = num
        backtrack(index + 1)
        used[j] = False  # Reset for other branches

3. Using Mutable Default Arguments

The Pitfall: If implementing with default parameters, using mutable defaults:

# WRONG - mutable default argument
def backtrack(index=0, current=[], used=[False]*n):
    # ...

Why It's a Problem: Mutable default arguments in Python are created once when the function is defined, not each time it's called. This causes state to persist between different calls to permute().

The Solution: Either use None as default and create new objects inside the function, or avoid default parameters entirely for mutable objects:

# CORRECT - initialize inside the function
def backtrack(index=0, current=None, used=None):
    if current is None:
        current = []
    if used is None:
        used = [False] * n
    # ...