Problem overview
The function permute(nums []int) [][]int receives a slice of distinct integers and returns every permutation: every way to put all the numbers in a row, each used exactly once.
The order of the answer is fixed. The positions are filled from first to last, and the numbers are always tried in their order in nums. Every permutation that starts with nums[0] comes first, then every one that starts with nums[1], and so on; among permutations with the same first number, the second number decides the same way. So nums itself comes first and nums reversed comes 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]]. For nums = [3, 1, 2] it is [[3, 1, 2], [3, 2, 1], [1, 3, 2], [1, 2, 3], [2, 3, 1], [2, 1, 3]]. The numbers are tried in the order 3, 1, 2, not in ascending order.
Approach: fill one position at a time
With n numbers there are n! permutations: 6 for three numbers, 40,320 for eight. Whatever the method, the answer is that big, so the aim is to produce each permutation once without wasted work.
Backtracking builds a permutation position by position in a slice current, and keeps a slice of booleans, used, that says which numbers current already holds:
- When
currenthas as many numbers asnums, it is a whole permutation: save a copy of it. - Otherwise, go through the numbers from index 0 and skip the used ones. For each free number, take it (mark it used, append it to
current), recurse to fill the remaining positions, then give it back (remove it, mark it unused) so the next number can take its place.
Because the loop always starts at index 0 and moves up, the numbers are tried in their order in nums, which gives exactly the order the statement asks for.
Step by step
- Create
resultas an empty[][]int, written[][]int{}. Each element is a permutation. - Create
usedwithmake([]bool, len(nums)).used[i]says whethernums[i]is already in the permutation being built.makesets every element tofalse, the zero value of abool. - Start the search with
backtrack(nums, used, []int{}, &result). No position is filled, so the permutation so far is empty. The last argument is the address ofresult, because the helper has to store the grown slice thatappendreturns. - Return
resultafter the call. - Declare the helper
backtrack(nums []int, used []bool, current []int, result *[][]int), returning nothing. - Base case. If
len(current) == len(nums),currentholds every number once. - Save a copy with
*result = append(*result, append([]int{}, current...))andreturn. - Loop over the candidates with
for i := 0; i < len(nums); i++. Always starting at 0 is what produces the required order. - Skip used numbers with
if used[i] { continue }. A number already incurrentcan't appear twice. - Mark it: set
used[i]totrue, so the deeper calls won't take it. - Append it:
current = append(current, nums[i])fills the next position. - Recurse with
backtrack(nums, used, current, result)to fill the rest.resultis already a pointer, so it is passed on as it is. - Remove it:
current = current[:len(current)-1]drops the last number. - Unmark it: set
used[i]back tofalse, so later permutations can usenums[i]in another position.
The solution in Go
func permute(nums []int) [][]int {
result := [][]int{}
used := make([]bool, len(nums))
backtrack(nums, used, []int{}, &result)
return result
}
func backtrack(nums []int, used []bool, current []int, result *[][]int) {
if len(current) == len(nums) {
*result = append(*result, append([]int{}, current...))
return
}
for i := 0; i < len(nums); i++ {
if used[i] {
continue
}
used[i] = true
current = append(current, nums[i])
backtrack(nums, used, current, result)
current = current[:len(current)-1]
used[i] = false
}
}The Go details worth a closer look:
- Slice headers and shared arrays. A slice value is a small header (pointer, length, capacity).
usedis passed as a header too, but both headers point to the same array, soused[i] = truein a deep call is seen by every caller. That is what lets the marks work.resultis different:appendmay return a header for a new array, so it travels as a pointer,*[][]int. - Why the copy matters.
append([]int{}, current...)builds a slice with its own array. Savingcurrentitself stores a slice that may share memory with later calls. For[1, 2, 3]that happens to work, but for[1, 2, 3, 4]the output has 24 entries where[1 2 4 3]appears twice and[1 2 3 4]never does. - The undo line. Inside one call,
currentgrows by one number on each turn of the loop. Trimming it back to its old length before the next turn is what lets the next candidate take the same position. - The classic loop. Go's
for i := 0; i < len(nums); i++has an init statement, a condition and a post statement, with no parentheses. continue. It ends the current turn of the loop and goes on with the nexti.makeversus a literal.make([]bool, len(nums))makes a slice whose length is only known at run time, with every elementfalse.
Complexity
Time: O(n · n!). There are n! permutations, and saving each one copies n numbers. The calls that build them are fewer than e · n! in all, and each call loops over the n numbers, which stays within the same bound.
Space: O(n) besides the answer. current and used hold at most n items and the recursion is at most n + 1 calls deep. The answer itself holds n · n! numbers, but that is the output.
Edge cases and common mistakes
- One number.
[1]gives[[1]]: a single number can be arranged in only one way. - Order of the numbers. The loop follows the order of
nums, so[3, 1, 2]starts with[3, 1, 2]and ends with[2, 1, 3]. Sortingnumsfirst would change the answer. - Forgetting to unmark. If
used[i]is never set back tofalse, the number stays blocked for every later branch, and most permutations never get built. - Forgetting to remove from
current. The next candidate would be appended after the previous one, so the permutations that follow would start with the wrong numbers. - Saving
currentwithout a copy. It can pass small tests and fail on larger ones, since it depends on how much capacityappendallocated. - Starting the loop at
i + 1. That is the pattern for subsets and combinations, where order doesn't matter. Permutations need every unused number at every position, so the loop starts at 0. - Forgetting the pointer. If
resultwere passed by value, the permutations appended insidebacktrackwould be lost when it returns. - Size. Eight numbers already give 40,320 permutations. Each extra number multiplies the count by the new length.
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]].[1, 2, 3, 4, 5, 6, 7, 8]gives 40,320 permutations.
