Permutations

Medium

The problem

Given a list of different numbers, return every way to arrange them in a row. The arrangements can come in any order.

Example 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]]
3 numbers give 3 × 2 × 1 = 6 arrangements.
Example 2
Input: nums = [1]
Output: [[1]]

Limits

1 ≤ nums.length ≤ 8
-10 ≤ nums[i] ≤ 10
All numbers are different
The order of the arrangements does not matter

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

At every position you may place any number that has not been used yet.

The idea

DFS with a used[] array (or swap in place); when the path length equals n record it.

Target: O(n · n!) time

Go function shape

func permute(nums []int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// Permutations: every ordering of distinct numbers.
// A `used` array replaces `start`: any unused element may go next.
func Permutations(nums []int) [][]int {
	res := [][]int{}
	path := make([]int, 0, len(nums))
	used := make([]bool, len(nums))
	var dfs func()
	dfs = func() {
		if len(path) == len(nums) {
			res = append(res, append([]int(nil), path...)) // copy!
			return
		}
		for i := range nums {
			if used[i] {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			dfs()
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs()
	return res
}

Read the lesson: Backtracking