loading

46. Permutations — Step-by-Step Visualization

mediumLeetCode #46ArrayBacktracking

Given an array `nums` of distinct integers, return all the possible permutations. You can 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]]`

Algorithm Pattern

Backtracking / DFS

Key Idea

We build permutations one number at a time. At each step, we pick one 'unused' number from the source array, add it to our current path, and recurse. Once we explore that path, we 'backtrack' by removing the number to try a different candidate.

Step-by-Step Approach

  1. Initialize an empty list `res` and a boolean array `used`.
  2. In the backtrack function:
  3. 1. If the length of `curr` equals the length of `nums`, add a copy of `curr` to `res`.
  4. 2. Loop through every index `i` in `nums`.
  5. 3. If `used[i]` is False:
  6. - Mark `used[i] = True` and add `nums[i]` to `curr`.
  7. - Recurse to build the rest of the permutation.
  8. - 'Backtrack': remove `nums[i]` from `curr` and mark `used[i] = False`.

Common Gotchas

  • Always add a *copy* of the current permutation to the result, otherwise, future modifications will affect the saved entries.
  • The source array must have distinct integers; if there are duplicates, a different approach (e.g. sorting + skipping) is needed.

Related Problems

← All problems