Permutations medium
Description
Given an array nums of distinct integers, return all possible permutations. You may return the answer in any order.
Examples
> Case 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]]
# 6 permutations — 3! = 6
> Case 2:
Input: nums = [0, 1]
Output: [[0,1], [1,0]]Constraints
1 <= nums.length <= 6- All elements of
numsare unique.
Intuition
A permutation is an ordering of all elements. To build one:
- Pick an element from the unused ones.
- Recurse on the remaining unused elements.
- When everything is used, the current sequence is a complete permutation.
The recursion tree branches by n at the root, n-1 at the next level, then n-2, all the way down to 1 — giving us n! leaves, which is exactly the number of permutations.
Decision tree for n = 3
[]
/ | \
pick 1 pick 2 pick 3
[1] [2] [3]
/ \ / \ / \
pick 2 pick 3 pick 1 pick 3 pick 1 pick 2
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
pick 3 pick 2 pick 3 pick 1 pick 2 pick 1
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]Six leaves → six permutations. Notice how the forbidden picks at each level are exactly the elements already used.
Approach 1: Backtracking with a used array
The standard pattern. We carry a used[] array that tracks which indices are already in the current permutation.
The “do the action → recurse → undo the action” sandwich is the backtracking template. You’ll see it again in every backtracking problem: N-Queens, Sudoku, Word Search. Once you internalize it, those problems all become variations of the same shape.
Approach 2: In-place swap
A clever variant that avoids the used array. At each level, we swap an unused element into the current position, recurse, then swap back. No extra space beyond the call stack.
The swap-based version is a touch faster (no used[] reads / writes) but slightly more cryptic.
Analysis
- Time: O(n · n!) — there are
n!permutations, and copying each to the output is O(n). - Space: O(n) for the call stack and the working permutation (output size is O(n · n!) and unavoidable).
What about duplicates?
If nums can contain duplicates (LeetCode’s Permutations II), the trick is to sort the array first, then skip an index i if nums[i] == nums[i-1] and i-1 is not currently used. That eliminates duplicate permutations at the source.
def permute_unique(nums):
result = []
nums.sort()
used = [False] * len(nums)
def backtrack(current):
if len(current) == len(nums):
result.append(current[:]); return
for i in range(len(nums)):
if used[i]: continue
# skip duplicates: pick the leftmost copy first
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
used[i] = True; current.append(nums[i])
backtrack(current)
current.pop(); used[i] = False
backtrack([])
return resultThat extra two-line guard is the entire difference between the two problems. The backtracking template stays the same.