46. 全排列

题目#

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路#

递归、深度优先、回溯

代码#

func permute(nums []int) [][]int {
    res := [][]int{}
    visited := map[int]bool{}

    // 深度优先
    var dfs func([]int)
    dfs = func(path []int) {
        // 如果是一个解
        if len(path) == len(nums) {
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
            return
        }

        // 遍历
        for _, n := range nums {
            // 访问过就跳过
            if visited[n] {
                continue
            }
            // 未访问过就尝试添加这一节点
            path = append(path, n)
            visited[n]=true

            // 递归
            dfs(path)

            // 回溯
            path = path[:len(path)-1]
            visited[n] = false
        }
    }

    dfs([]int{})

    return res
}