39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
输入：candidates = [2,3,6,7],target = 7,candidates 中的数字可以无限制重复被选取。
说明：

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

所求解集为：
[ [7],[2,2,3] ]

回到本题，我们定义递归函数 dfs(target, combine, idx) 表示当前在 candidates 数组的第 idx 位，还剩 target 要组合，已经组合的列表为 combine。递归的终止条件为 target <= 0 或者 candidates 数组被全部用完。那么在当前的函数中，每次我们可以选择跳过不用第 idx 个数，即执行 dfs(target, combine, idx + 1)。也可以选择使用第 idx 个数，即执行 dfs(target - candidates[idx], combine, idx)，注意到每个数字可以被无限制重复选取，因此搜索的下标仍为 idx。
image.png
复杂度分析

  • 时间复杂度：O(S)，其中 S 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 O(n × 2^n) 是一个比较松的上界，即在这份代码中，n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 target - candidates[idx] >= 0 进行剪枝，所以实际运行情况是远远小于这个上界的。

  • 空间复杂度：O(target)。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 O(target) 层。
    ```go // func combinationSum(candidates []int, target int) [][]int { res := [][]int{} var dfs func(start int, temp []int, sum int) //1，start是当前选择的起点索引 = index；是否使用idx=核心

    1.                                               //temp是当前的集合，顺序的哈 = combine 【2，2，3】
    2.                                               //sum是当前求和 = 迷你target   7-2=5

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

      if sum >= target {                        //开ds始回溯条件，sum<target
      if sum == target {                        //2, temp的拷贝 加入解集
          newTmp := make([]int, len(temp))
          copy(newTmp, temp)
          res = append(res, newTmp)            
      }
      return                        //3, 结束当前递归，返回什么❓res？== 退出函数符号，执行过程，不指定返回值
  }

  for i := start; i < len(candidates); i++ {        //4, 枚举当前可选的数，从start开始，回溯开始；要用🌲形状理解
      temp = append(temp, candidates[i])            // 选这个数
      dfs(i, temp, sum+candidates[i])                // 递归，基于此继续选择，传i，下一次就不会选到i左边的数
      temp = temp[:len(temp)-1]        //5, 撤销选择，回到选择candidates[i]之前的状态，继续尝试选同层右边的数
  }

    }

    dfs(0, []int{}, 0) //6, 最开始可选的数是从第0项开始的，传入一个空集合，sum也为0 return res //最终答案 [2,2,3],[2,5][7] }

```

  • ×：当前组合和之前生成的组合重复了，比如最左边的×: 2232，与之前生成过的2223重复（虽然后者因为>target而被舍弃）
  • △：当前求和 > target，不能选下去了，返回。
  • ○：求和正好 == target，加入解集，并返回。