LeetCode 40 组合总和 II

题目链接：

https://leetcode.cn/problems/combination-sum-ii/

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

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)  // 将候选人排序
    var res [][]int
    var path []int
    backtrack(candidates, target, &res, &path, 0)
    return res
}

func backtrack(candidates []int, target int, res *[][]int, path *[]int, start int) {
    if target == 0 {
        tmp := make([]int, len(*path))
        copy(tmp, *path)
        *res = append(*res, tmp)
        return
    }
    for i := start; i < len(candidates); i++ {
        if i > start && candidates[i] == candidates[i-1] {  // 去重
            continue
        }
        if candidates[i] > target {  // 剪枝
            break
        }
        *path = append(*path, candidates[i])
        backtrack(candidates, target-candidates[i], res, path, i+1)
        *path = (*path)[:len(*path)-1]
    }
}

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

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

通过测试用例：176 / 176

题解：

这是一个典型的组合求和问题。我们可以使用回溯算法来解决它。回溯算法是一种通过不断尝试来找到所有解的算法，它通过深度优先遍历搜索所有可能的解。在这个问题中，我们可以使用一个递归函数来实现回溯算法。函数的参数包括当前已经组成的数组、剩余的候选人、当前的和以及目标和。每次递归调用时，我们将当前候选人中的一个数字加入到当前已经组成的数组中，并更新剩余的候选人、当前的和以及目标和，然后再次递归调用函数。如果当前的和等于目标和，那么将当前已经组成的数组加入到结果集中，并回溯到上一层调用。如果当前的和大于目标和，也回溯到上一层调用。如果当前的候选人已经为空，那么也回溯到上一层调用。

在这个代码中，我们首先将候选人数组排序，然后调用 backtrack 函数进行回溯。在 backtrack 函数中，如果目标和为0，我们将当前已经组成的数组加入到结果集中，并返回上一层调用。否则，我们遍历当前的候选人数组，如果当前的数字和上一个数字相同，则跳过，以去重。如果当前的数字大于目标和，则跳过，以剪枝。否则，将当前的数字加入到已经组成的数组中，并递归调用 backtrack 函数。在递归调用完成后，我们将当前的数字从已经组成的数组中删除，以回溯到上一层调用。

这样，我们就完成了组合求和问题的解决。