LeetCode 47 全排列 II

题目链接：

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

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

func permuteUnique(nums []int) [][]int {
  var res [][]int
  used := make([]bool, len(nums))
  sort.Ints(nums) // 先对数组进行排序，方便后面剪枝
  backtrack(nums, &res, []int{}, used)
  return res
}

func backtrack(nums []int, res *[][]int, path []int, used []bool) {
  if len(path) == len(nums) {
    tmp := make([]int, len(path))
    copy(tmp, path)
    *res = append(*res, tmp)
    return
  }
  for i := 0; i < len(nums); i++ {
    // 如果当前数字已经使用过，则跳过
    if used[i] {
      continue
    }
    // 如果当前数字与前一个数字相同，且前一个数字没有使用过，剪枝
    if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
      continue
    }
    path = append(path, nums[i])
    used[i] = true
    backtrack(nums, res, path, used)
    used[i] = false
    path = path[:len(path)-1]
  }
}

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

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

通过测试用例：33 / 33

题解：

这是一道典型的回溯算法题目。 回溯算法的思路是一边搜索一边回溯，遇到不合适的情况就回溯，搜索全部的情况。这里我们可以按照如下步骤实现：

1. 首先判断输入的数组长度，如果为空则直接返回空列表。
2. 创建一个空列表用于存储结果，创建一个空列表 used 用于存储数字是否已经使用过。
3. 编写一个递归函数 backtrack ，该函数的参数是当前生成的排列 nums 和当前处理到的位置 pos 。
4. 当 pos 的值等于数组的长度时，将当前的 nums 加入结果列表中。
5. 遍历数组 nums ，判断数字是否已经使用过，如果使用过则跳过。
6. 如果数字没有使用过，则将其添加到当前的 nums 中，并将 used 的对应位置标记为 True 。
7. 继续递归 backtrack ，处理下一个位置的数字。
8. 回溯过程，将 used 对应位置标记为 False ，并将当前位置的数字从 nums 中删除。

在上面的代码中，我们定义了两个函数 permuteUnique 和 backtrack，其中 permuteUnique 函数是主函数，用于调用 backtrack 函数进行排列的生成。backtrack 函数是递归函数，用于生成排列。

我们首先对输入数组进行排序，这样能够方便后面的剪枝操作。然后调用 backtrack 函数，该函数的参数包括当前处理到的数组 nums、当前生成的排列 res、当前已经生成的排列 path 和数字是否已经使用过 used。

在 backtrack 函数中，如果当前排列的长度已经等于数组的长度，说明已经生成了一个排列，将其加入到结果列表 res 中，并返回。否则遍历数组 nums，如果当前数字已经使用过，则跳过。如果当前数字与前一个数字相同，且前一个数字没有使用过，则剪枝，避免生成重复的排列。如果数字没有使用过，则将其添加到当前的排列 path 中，并将 used 的对应位置标记为 True。然后递归调用 backtrack 函数，处理下一个位置的数字。回溯过程中，将 used 的对应位置标记为 False，并将当前位置的数字从 path 中删除。

最后，将结果列表 res 返回即可。

时间复杂度分析

回溯算法的时间复杂度很难精确地计算，因为它会遍历所有的可能性。在本题中，时间复杂度取决于排列的数量。如果输入数组中有重复的数字，则会影响排列的数量。但是，可以通过剪枝操作来避免生成重复的排列，从而减少回溯的次数。因此，这里我们可以认为时间复杂度是 O(n*n!)，其中 n 是输入数组的长度。