Problem overview
permute receives nums, an array of distinct integers, and returns every permutation: every way to put all the numbers in a row, each exactly once. The order of the answer is fixed. Positions are filled from first to last, and the numbers are always tried in their order in nums. All permutations starting with nums[0] come first, then those starting with nums[1], and so on; among permutations with the same first number, the second number decides in the same way. So nums itself is first and nums reversed is last.
For nums = [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 1, the numbers left are 2 and 3, tried in that order. For nums = [3, 1, 2] the numbers are tried as 3, then 1, then 2, not in ascending order, so the answer is [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]].
Approach: fill one position at a time
Build a permutation position by position in a list current. For the next position, go through the numbers of nums in order and skip the ones current already holds. For each free number:
- take it: mark it as used and add it to
current; - fill the remaining positions with a recursive call;
- give it back: remove it from
currentand unmark it, so the next number can take its place.
When current holds as many numbers as nums, it contains every number once, so it is a whole permutation and a copy is saved. Trying the numbers in their order in nums at every position produces exactly the order the task asks for.
The marks live in an array used of true/false values, one per number: used[i] says whether nums[i] is already in current. Marking by index rather than by value is simple, and since the numbers are distinct, it is also unambiguous.
Step by step
- Create
resultas an empty[[Int]]. - Create
usedas[Bool](repeating: false, count: nums.count): onefalseper number, because nothing is taken yet. - Create
currentas an empty[Int], the permutation being built. - Start the search with
backtrack(nums, &used, ¤t, &result). The&lets the call change the three variables themselves. - Return
result. The helper added every permutation to it. - Write the helper
backtrackin the class, withused,currentandresultasinoutparameters. Each call fills one more position and calls itself for the rest. - Base case: check
current.count == nums.count. - Save and stop: append
currenttoresultandreturn. - Loop over the candidates with
for i in 0..<nums.count. Always starting at 0 and going in order is what gives the required order. - Skip taken numbers: if
used[i]is true,continue. A number already incurrentcan't appear twice. - Mark it by setting
used[i]totrue, so deeper calls won't take it. - Append
nums[i]tocurrent: this fills the next position. - Recurse with the same arguments to fill the rest.
- Undo the append with
current.removeLast(). - Unmark by setting
used[i]back tofalse, so permutations built later can usenums[i]in another position.
The solution in Swift
class Solution {
func permute(_ nums: [Int]) -> [[Int]] {
var result = [[Int]]()
var used = [Bool](repeating: false, count: nums.count)
var current = [Int]()
backtrack(nums, &used, ¤t, &result)
return result
}
func backtrack(_ nums: [Int], _ used: inout [Bool], _ current: inout [Int], _ result: inout [[Int]]) {
if current.count == nums.count {
result.append(current)
return
}
for i in 0..<nums.count {
if used[i] {
continue
}
used[i] = true
current.append(nums[i])
backtrack(nums, &used, ¤t, &result)
current.removeLast()
used[i] = false
}
}
}
Swift details worth knowing:
inoutparameters. A function normally can't change its parameters.inouthands it the caller's variable to change, and the call site marks each one with&. Without it, callingappendonresultinside the helper is a compile error.[Bool](repeating: false, count: n)builds an array ofncopies of one value:repeating:is the value andcount:is how many.0..<nums.countis a half-open range that stops beforenums.count, soiis always a valid index. The closed form0...nums.countwould include an index one past the end and crash onused[i].- Arrays are values.
result.append(current)stores a copy ofcurrentas it is now, so the laterremoveLast()calls leave the saved permutations alone. continueskips the rest of the current turn of the loop and goes on with the nexti.
Complexity
Time: O(n · n!). There are n! permutations, and saving each copies n numbers. The calls that build them number fewer than e · n! in all, and each call loops over the n numbers, which also gives O(n · n!).
Space: O(n) extra, not counting the answer: current and used hold at most n items, and the recursion is n + 1 calls deep.
Edge cases and common mistakes
- One number.
[1]gives[[1]]. The first call takes the number, the second call findscurrentfull and saves it. - Forgetting to unmark. If
used[i]is never set back tofalse, numbers stay blocked after their first use, and most permutations are never found. - Forgetting
removeLast().currentthen keeps numbers from earlier branches and the length checkcurrent.count == nums.countfires at the wrong time. - Sorting the input. The numbers are tried in their order in
nums. For[3, 1, 2]the first permutation is[3, 1, 2], and sorting first would give a different order. - Counting. A list of 4 numbers has 24 permutations, 5 has 120, and the largest input here, 8 numbers, has 40,320.
- Two numbers.
[2, 1]gives[[2, 1], [1, 2]]: the answer follows the order ofnums, not ascending order.
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]].[2, 1]gives[[2, 1], [1, 2]].[1, 2, 3, 4]gives 24 permutations and[1, 2, 3, 4, 5, 6, 7, 8]gives 40,320.
