40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[ [1,2,2], [5] ]

对比第 39 题

39题：元素可以重复使用，组合不能重复。
本题：元素不可以重复使用，组合不能重复。
image.png

  • 时间复杂度： DFS 回溯算法通常是指数级别的复杂度（因此数据范围通常为 30 以内）。这里暂定 O(n * 2^n)

  • 空间复杂度：同上。复杂度为 O(n * 2^n) ```go // func combinationSum2(candidates []int, target int) [][]int { sort.Ints(candidates) //多的排序部分，防重复 res := [][]int{}

    var dfs func(start int, temp []int, sum int) dfs = func(start int, temp []int, sum int) {

    1.   if sum >= target {
    2.       if sum == target {
    3.           newTmp := make([]int, len(temp))
    4.           copy(newTmp, temp)
    5.           res = append(res, newTmp)
    6.       }
    7.       return
    8.   }
    9.   for i := start; i < len(candidates); i++ {
    10.       if i-1 >= start && candidates[i-1] == candidates[i] {
    11.           continue                                //多的一部分，用来判断元素的重复，直接跳出for循环了
    12.       }
    14.       temp = append(temp, candidates[i])
    15.       dfs(i+1, temp, sum+candidates[i])            //从i+1开始递归，不是i
    16.       temp = temp[:len(temp)-1]
    17.   }

    } dfs(0, []int{}, 0) return res }

``` image.png