Problem overview
permute receives a Vec<i32> of distinct numbers named nums and returns every permutation: every way to put all the numbers in a row, each exactly once. The order of the answer is fixed. You fill the positions from first to last and always try the numbers in their order in nums. All permutations that start with nums[0] come first, then all that start with nums[1], and so on, and inside each group the second number decides the same way.
For [1, 2, 3] the answer is:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Two permutations start with 1, two with 2 and two with 3. After a 1, the numbers left are 2 and 3, tried in that order, so [1, 2, 3] comes before [1, 3, 2]. The order follows nums, not ascending order: for [3, 1, 2] the answer starts with [3, 1, 2], [3, 2, 1] and then [1, 3, 2].
Approach: fill one position at a time
There are n! permutations: n choices for the first position, n - 1 for the second, and so on. For eight numbers that is 40,320.
Backtracking builds each permutation in a vector current. A second vector, used, holds one true/false value per number and says which numbers current already contains. To fill the next position, go through the numbers in order, skip the used ones, and for each free number:
- Take it: mark it used and add it to
current. - Recurse to fill the remaining positions.
- Give it back: remove it from
currentand mark it unused, so the next number can take its place.
When current holds as many numbers as nums, it is a whole permutation, and a copy goes into the result. Because the loop always starts at index 0 and goes up, the numbers are tried in the order of nums, which gives exactly the required order.
Step by step
- Create
resultas a mutableVec::new(). Its type,Vec<Vec<i32>>, is inferred from how it is used. - Create
usedasvec![false; nums.len()]:vec![value; n]makesncopies ofvalue.used[i]says whethernums[i]is in the permutation being built. - Start the search:
Self::backtrack(&nums, &mut used, &mut Vec::new(), &mut result). No position is filled yet, so the permutation being built is empty and every number is free. - Return
resultwith no semicolon. - Write the helper
backtrackwithnums,used,currentandresult. Each call fills one more position and calls itself for the rest. - Check whether
currentis full:current.len() == nums.len(). Then it holds every number once. - Save a snapshot with
result.push(current.clone()), thenreturn.currentkeeps changing, so the result needs its own copy. - Loop with
for i in 0..nums.len(). The range stops beforenums.len(), soiis always a valid index. - Skip used numbers: if
used[i]is true,continuegoes on with the nexti. - Mark the number:
used[i] = true. Deeper calls see the mark and will not take it again. - Add it:
current.push(nums[i]). - Recurse with the same four arguments to fill the remaining positions.
- Remove it:
current.pop(). - Unmark it:
used[i] = false. Nownums[i]is free for permutations built later.
The solution in Rust
impl Solution {
fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut result = Vec::new();
let mut used = vec![false; nums.len()];
Self::backtrack(&nums, &mut used, &mut Vec::new(), &mut result);
result
}
fn backtrack(nums: &Vec<i32>, used: &mut Vec<bool>, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
if current.len() == nums.len() {
result.push(current.clone());
return;
}
for i in 0..nums.len() {
if used[i] {
continue;
}
used[i] = true;
current.push(nums[i]);
Self::backtrack(nums, used, current, result);
current.pop();
used[i] = false;
}
}
}
The Rust details worth a closer look:
- Borrowing.
&numslends the numbers for reading, and&mut used,&mut Vec::new()and&mut resultlend vectors the call may change. Insidebacktrackthese are already references, so they are passed down unchanged. clone()for the snapshot.currentis a borrowed&mut Vec<i32>, andresultneeds owned vectors.current.clone()makes a new vector with the same numbers, so later changes tocurrentdo not touch what was saved.for i in 0..nums.len(). The range0..nexcludesn. The loop uses an index, not the numbers themselves, becauseused[i]andnums[i]must stay in step.continue. It skips the rest of the current turn of the loop, which here means everything below theif.- Vector of flags.
vec![false; nums.len()]is aVec<bool>. Its length matchesnums, soused[i]never goes out of bounds. - Return value.
resulthas no semicolon, sopermutereturns it.
Complexity
Time: O(n · n!). There are n! permutations, and copying each one takes n steps. The recursion makes fewer than e · n! calls in all, and each call loops over the n numbers, so the total stays within O(n · n!).
Space: O(n) besides the answer. current and used hold at most n values each, and the recursion is at most n + 1 calls deep. The answer is not counted.
Edge cases and common mistakes
- One number.
[1]gives[[1]]. The first call loops once, takes the number and saves it. - Order of the numbers. The answer follows the order of
nums.[3, 1, 2]gives[[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]]. Sortingnumsfirst would produce a different order. - Forgetting to unmark. If
used[i]stays true after the call, the number looks taken forever and the search misses permutations. - Forgetting
pop().currentkeeps growing, so it never has the right length and the numbers repeat. - Looping from the current position. Each position must try all the unused numbers, starting from index 0, not only the ones after the last taken index. A loop starting at
i + 1is the right idea for subsets, not for permutations. - Saving
currentwithout a copy. It does not compile (result.push(current)has the wrong type), and a copy is what keeps the saved permutation from changing later.
Testing
[1, 2, 3]gives[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].[3, 1, 2]gives[[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]].[1]gives[[1]].- Four distinct numbers give 24 permutations, and eight give 40,320.
