题目

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8
所求解集为:

  1. [
  2.     [1, 7],
  3.     [1, 2, 5],
  4.     [2, 6],
  5.     [1, 1, 6]
  6. ]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5
所求解集为:

[
    [1,2,2],
    [5]
]

方案（回溯）

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)

    var res [][]int
    dfs(candidates, []int{}, 0, target, 0, &res)
    return res
}

// sum - sum(path)
// i - 遍历到的索引
func dfs(candidates, path []int, sum, target, i int, res *[][]int) {
    if sum > target {
        return
    }
    if sum == target {
        dst := make([]int, len(path))
        copy(dst, path)
        *res = append(*res, dst)
        return
    }

    for i < len(candidates) {
        sum += candidates[i]
        path = append(path, candidates[i])
        i += 1
        dfs(candidates, path, sum, target, i, res)
        sum -= candidates[i-1]
        path = path[:len(path)-1]

        // 剪枝，回溯之后，如果数字出现重复则结果也会出现重复
        for i > 0 && i < len(candidates) && candidates[i] == candidates[i-1] {
            i += 1
            continue
        }
    }
}

原文

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