📑 题目：39. 组合总和

🚀 本题 LeetCode 传送门

题目大意

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

candidates 中的数字可以无限制重复被选取。

解题思路

  • 题目要求出总和为 sum 的所有组合，组合需要去重。
  • 这一题和第 47 题类似，只不过元素可以反复使用。

代码

  1. package leetcode
  3. import ""sort""
  5. func combinationSum(candidates []int, target int) [][]int {
  6.  if len(candidates) == 0 {
  7.   return [][]int{}
  8.  }
  9.  c, res := []int{}, [][]int{}
  10.  sort.Ints(candidates)
  11.  findcombinationSum(candidates, target, 0, c, &res)
  12.  return res
  13. }
  15. func findcombinationSum(nums []int, target, index int, c []int, res *[][]int) {
  16.  if target <= 0 {
  17.   if target == 0 {
  18.    b := make([]int, len(c))
  19.    copy(b, c)
  20.    *res = append(*res, b)
  21.   }
  22.   return
  23.  }
  24.  for i := index; i < len(nums); i++ {
  25.   if nums[i] > target { // 这里可以剪枝优化
  26.    break
  27.   }
  28.   c = append(c, nums[i])
  29.   findcombinationSum(nums, target-nums[i], i, c, res) // 注意这里迭代的时候 index 依旧不变，因为一个元素可以取多次
  30.   c = c[:len(c)-1]
  31.  }
  32. }