LeetCode 46 全排列

题目链接：

https://leetcode.cn/problems/permutations/

以下是使用Go语言实现外观数列问题的代码：

func permute(nums []int) [][]int {
    var res [][]int
    visited := make([]bool, len(nums))
    backtrack(nums, []int{}, visited, &res)
    return res
}

func backtrack(nums []int, path []int, visited []bool, res *[][]int) {
    if len(path) == len(nums) {
        // path已经包含了所有元素，将其添加到结果中
        *res = append(*res, append([]int{}, path...))
        return
    }
    for i := 0; i < len(nums); i++ {
        if visited[i] {
            continue
        }
        visited[i] = true
        path = append(path, nums[i])
        backtrack(nums, path, visited, res)
        path = path[:len(path)-1]
        visited[i] = false
    }
}

执行用时：4 ms, 在所有 Go 提交中击败了32.44%的用户

内存消耗：2.5 MB, 在所有 Go 提交中击败了29.80%的用户

通过测试用例：26 / 26

题解：

这道题是典型的回溯算法，用于解决在一组可能的解中找到所需解的问题。

在回溯算法中，我们从一个可能的“状态”开始，然后尝试在这种状态下做出选择。一旦我们做出选择，我们会继续前进，直到我们到达了一个无法继续前进的状态。此时，我们需要回到前一个状态并尝试其他选择，直到找到所需的解决方案或遍历了所有可能的状态。

对于此题，我们可以从一个空的排列开始，将数组中的每个元素依次添加到排列中。当排列的长度等于数组的长度时，我们就得到了一个完整的排列，将其添加到结果列表中。

算法实现

具体实现过程中，我们可以用一个visited数组来记录已经选择过的元素。在回溯的过程中，当我们选择了一个元素，就将其标记为已访问，并将其添加到当前排列中。接着，我们继续递归地搜索排列，直到排列的长度等于数组的长度。此时，我们将排列添加到结果列表中，并将其从当前排列中移除。最后，我们将该元素标记为未访问，以便后续可以选择它。

首先，我们定义了一个permute函数，该函数接受一个整数数组nums并返回其所有可能的全排列。在函数内部，我们创建了一个结果列表res，一个布尔类型的visited数组来记录已访问过的元素。

接下来，我们调用backtrack函数进行回溯搜索。backtrack函数接受四个参数：nums表示给定的整数数组，path表示当前排列，visited表示已访问的元素，res表示结果列表。

在backtrack函数中，我们首先检查当前排列是否已经包含了所有元素。如果是，我们将该排列添加到结果列表中，并返回。

接着，我们遍历数组中的每个元素。如果该元素已被访问过，我们就跳过它。否则，我们将其标记为已访问，并将其添加到当前排列中。接着，我们递归地搜索剩下的元素，直到找到所有可能的排列。搜索完毕后，我们将当前元素从排列中移除，并将其标记为未访问，以便后续可以选择它。

最后，我们在permute函数中调用backtrack函数，并将结果列表返回。