Generate Permutations

LeetCode 46 · View on LeetCode

Generate all permutations using the swap-based approach. At each position, swap in every remaining element, recurse, then swap back to restore order.

package main

import "fmt"

func permute(nums []int) [][]int {
	result := [][]int{}

	var backtrack func(start int)
	backtrack = func(start int) {
		if start == len(nums) {
			tmp := make([]int, len(nums))
			copy(tmp, nums)
			result = append(result, tmp)
			return
		}
		for i := start; i < len(nums); i++ {
			nums[start], nums[i] = nums[i], nums[start] // choose
			backtrack(start + 1)                          // explore
			nums[start], nums[i] = nums[i], nums[start] // unchoose
		}
	}

	backtrack(0)
	return result
}

func main() {
	fmt.Println(permute([]int{1, 2, 3}))
	// [[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]
}