46. 全排列

题目

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入：nums = [1,2,3]

输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入：nums = [0,1]

输出：[[0,1],[1,0]]

复杂度

回溯

• 时间复杂度：\(O(n⋅n!)\)。
  • \(n\) 为数组 nums 的长度，回溯的调用次数是 \(O(n!)\)，数组拼接操作使用 \(O(n)\)，因此总体时间复杂度为 \(O(n⋅n!)\)。
• 空间复杂度：\(O(n)\)。\(n\) 为数组 nums 的长度。

题解

Go

func permute(nums []int) [][]int {
    // 时间 O(n⋅n!)
    // 空间 O(n)
    res := make([][]int, 0)
    path := make([]int, 0, len(nums))
    state := make([]bool, len(nums))
    var dfs func(nums []int, curr int)
    dfs = func(nums []int, curr int) {
        if curr == len(nums) {
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
        }

        for i := 0; i < len(nums); i++ {
            if !state[i] { // 判断是否访问过
                path = append(path, nums[i])
                state[i] = true
                dfs(nums, curr+1)
                state[i] = false
                path = path[:len(path)-1]
            }
        }
    }

    dfs(nums, 0)
    return res
}

Python

class Solution:
    def permute(self, nums):
        result = []
        self.backtracking(nums, [], [False] * len(nums), result)
        return result

    def backtracking(self, nums, path, used, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtracking(nums, path, used, result)
            path.pop()
            used[i] = False