The problem
Given distinct numbers, return every possible ordering (permutation) of them.
Input: [1, 2, 3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Picture it
Picture seating guests in a row of chairs. For the first chair, any guest can sit. For the next chair, any guest not yet seated, and so on. The decision tree branches on “who sits next?”. When every chair is filled we write the seating down, then stand the last guest back up and try someone else.
How to recognise it
- The answer is every ordering of the input, so order matters (unlike subsets and combinations).
- Every item must be used exactly once in each answer.
- The input is tiny: at most 6 distinct numbers, giving at most 6! = 720 answers.
- The decision tree has a different number of branches at each level: n choices for the first position, n − 1 for the second, and so on.
- Because earlier choices remove options for later ones, you need a way to know what is already used. That is the core of backtracking for arrangements: choose an unused item, recurse, then give it back.
Start with brute force
Fill each of the n positions with any of the n numbers, then keep only the fillings that use every number once.
from itertools import product
def permute_brute(nums):
n = len(nums)
return [list(t) for t in product(nums, repeat=n)
if len(set(t)) == n]
This builds n^n candidate tuples, but only n! of them are real permutations. For n = 6 that is 6^6 = 46,656 candidates for 720 answers, and for n = 6 it still runs in a blink. The gap grows fast, though: for n = 10 it would be 10^10 candidates for 3,628,800 answers. Time is O(n · n^n) and space is O(n) beyond the output.
From brute force to the idea
- Find the waste. The brute force happily writes
[1, 1, 2]and only throws it away at the end. Most of the n^n candidates are rejected after being fully built. - Reject early. Build one position at a time. Before placing a number, check it is not already in the partial answer.
- Keep one shared partial answer.
seatis the list built so far. Appending a number seats a guest in the next chair. - Recurse, then undo. After
dfs()explores all arrangements of the remaining chairs,seat.pop()stands the guest up, so the next candidate starts from the same state. - Stop when full. When
len(seat) == len(nums)every chair is filled; save a copyseat[:].
This is the key idea: build the arrangement one chair at a time, skipping used numbers, and undo each choice after exploring it.
The key idea
Backtracking with a “used” set: choose, recurse, un-choose. n! orderings.
Python solution
def permute(nums):
res, seat = [], []
def dfs():
if len(seat) == len(nums):
res.append(seat[:]); return
for x in nums:
if x not in seat: # guest still standing
seat.append(x)
dfs()
seat.pop() # stand up again, try someone else
dfs()
return resIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all n^n fillings) | O(n · n^n): build and test each candidate | O(n) beyond the output |
| Backtracking (shown code) | O(n² · n!): about n! leaves, and each node loops n times with an O(n) in check on a list | O(n) beyond the output: the recursion and seat |
The x not in seat test scans a list. A set (or a list of booleans) for "used" would make each check O(1) and bring the time down to O(n · n!).
Edge cases
- One number (
[1]): returns[[1]]. - Three numbers (
[1, 2, 3]): returns the six orderings in the example, in that order. - Empty list: returns
[[]], the one empty arrangement. - Duplicates in the input (
[1, 1, 2]): thex not in seattest treats the two 1s as the same, so the seat never fills and the code returns[]. The problem promises distinct numbers. - Values: negative numbers and zero are fine, as long as they are distinct.
- Maximum size: 6 numbers produce 720 lists, and the recursion is 7 calls deep.
Common mistakes
- Forgetting
seat.pop(). Only the first arrangement is found:permute([1, 2, 3])returns just[[1, 2, 3]]. - Appending
seatinstead ofseat[:], so every result ends up as the same emptied list. - Starting the loop at a growing index, as in subsets. That finds combinations, not arrangements, because order is lost.
- Checking
x not in seatby position, not by value, which breaks when values repeat.
The input may now contain duplicates (for example [1, 1, 2]). Return every distinct ordering, with no repeated lists. Describe your approach, then write it if you like.
Compare with our answer
Track how many copies of each value are still unused, not which positions were used. At each chair, try each distinct value that still has copies left, so two equal values never start separate branches.
from collections import Counter
def permute_unique(nums):
counts = Counter(nums)
res, cur = [], []
def dfs():
if len(cur) == len(nums):
res.append(cur[:])
return
for x in counts: # each distinct value once
if counts[x] > 0:
counts[x] -= 1
cur.append(x)
dfs()
cur.pop()
counts[x] += 1
dfs()
return res
permute_unique([1, 1, 2]) returns [[1, 1, 2], [1, 2, 1], [2, 1, 1]]. Time is O(n · number of distinct permutations), space O(n) beyond the output.
A strong answer mentions: counting copies instead of marking positions, looping over distinct values so equal values never branch twice, and restoring the count after the recursive call.
1. A scheduler must list every possible order in which 5 distinct jobs can run. Which approach fits best?
Orders matter and every job appears exactly once, so each slot chooses among the jobs that are left: 5! = 120 orders. A take or leave choice produces subsets, not orders, and the other two give one answer.
2. What limits the shown code to roughly O(n² · n!) rather than O(n · n!)?
Each node loops over n numbers and each in test on a list can scan up to n entries. Copying costs only O(n) per leaf, popping the last element is O(1), and a used-set would remove the extra factor of n.
3. What does the shown permute return for [1, 1, 2]?
The test is by value: once a 1 is seated, neither 1 can be seated again, so only two chairs can be filled and len(seat) == 3 never happens. The code never reaches the index or the result list.
Score 60% or more and the lesson is marked complete.