Permutations

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

Examples

• 1 ≤ nums.length ≤ 6
• -10 ≤ nums[i] ≤ 10
• All integers of nums are unique.

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion & Backtracking - Essential for exploring paths and undoing choices.
• Array Swapping - Needed to generate permutations efficiently in place.

1. Backtracking - Visited Array

Intuition

Think of this like building a team from a pool of players. You pick the first player, then pick the second from the remaining players, and so on.

To generate a permutation, we need to pick numbers one by one. But we cannot pick the same number twice in a single permutation. So, we iterate through the array and use a visited array (or boolean array) to keep track of which numbers are currently in our subset. If a number is already picked, we skip it. Once we build a subset of length n, we add it to our results.

Maintain:
res -> final list of permutations
curr -> current permutation being built
visited -> array or set tracking used elements

Define a recursive function backtrack():
  If len(curr) equals len(nums):
    Add a copy of curr to res
    Return
  
  For each num in nums:
    If num is in visited:
      Continue (skip this number)
    
    Add num to curr
    Mark num as visited
    Recurse: backtrack()
    
    Remove num from curr (backtrack)
    Mark num as unvisited (backtrack)

Start recursion with backtrack()
Return res

2. Backtracking - In-Place Swapping

Intuition

Instead of using extra memory (like a visited array) to keep track of what we've used, we can partition the array into two parts:

• Fixed part: The prefix of the array that is already part of the current permutation.
• Unused part: The suffix of the array containing numbers we can still choose.

At step start, we can choose any element from the unused part (from index start to n-1). We bring our chosen element to the start position by swapping it with whatever is currently at start. We then move on to start + 1. When we backtrack, we swap them back to restore the original order.

Maintain:
res -> final list of permutations

Define a recursive function backtrack(start):
  If start equals len(nums):
    Add a copy of nums to res
    Return
  
  For i from start to len(nums) - 1:
    Swap nums[start] and nums[i]
    
    Recurse: backtrack(start + 1)
    
    Swap nums[start] and nums[i] (undo swap to backtrack)

Start recursion with backtrack(0)
Return res

Time Complexity: O(N * N!) since we generate N! permutations and each takes O(N) time to copy.

Space Complexity: O(N) for the recursion stack (ignoring output space).

Common Pitfalls

Forgetting to Backtrack (Swap Back)

In the in-place swapping method, if you don't swap the elements back after the recursive call, the array becomes scrambled. You will end up generating incorrect, duplicate permutations instead of exploring all unique combinations. Always undo the swap!

nums[start], nums[i] = nums[i], nums[start]  # Swap backtrack(start + 1) nums[start], nums[i] = nums[i], nums[start]  # Must swap back!

Incorrect Base Case Reference

When you reach the base case start == len(nums), you must append a copy of the array to your results. If you append nums directly, every permutation in your result list will just be a reference to the same underlying array, which continues to get swapped and scrambled.

# WRONG res.append(nums) # CORRECT res.append(nums[:]) # Python res.add(new ArrayList<>(nums)) # Java