全排列

递归与回溯

说明

逐层选择一个尚未使用的元素；输出规模为 n!。

分析

递归的第 k 层决定结果第 k 个位置放什么，used 标记已经选择的元素。走到长度 n 时复制当前路径，否则回退选择后尝试下一候选。

图解推演

[1,2,3] 的第一层有 3 个选择，第二层剩 2 个，最后剩 1 个，共 6 个叶子。图中只展开首元素为 1 的分支。撤销 path 和 used 是成对操作；只撤销其中一个会漏解或重复使用同一位置。

查看图表代码

适用前提与边界

输出本身有 n! 个，输入稍大就会迅速增长；重复元素还需去重规则。

示例输入与调用

fmt.Println(Permutations([]int{1, 2, 3}))

运行输出

[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]]

完整 Go 示例

package main

import "fmt"

func Permutations(a []int) [][]int {
	out := [][]int{}
	used := make([]bool, len(a))
	path := []int{}
	var dfs func()
	dfs = func() {
		if len(path) == len(a) {
			out = append(out, append([]int(nil), path...))
			return
		}
		for i, x := range a {
			if used[i] {
				continue
			}
			used[i] = true
			path = append(path, x)
			dfs()
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	dfs()
	return out
}

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