给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

思路

  1. 动态规划，维护 0 ~ target 的计算结果，最终输出 dp[target]
  2. dp[n] = candidate X dp[n - candidate] 结果的并集，其中 candidate 为 dp[n - candidate] 中最大的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var combinationSum = function (candidates, target) {
  candidates = candidates.sort((a, b) => a - b)
  const dp = [[[]]]
  for (let i = 1; i <= target; ++i) {
    dp[i] = []
    for (const val of candidates) {
      if (val > i) {
        break
      }
      const itemsGroups = dp[i - val].filter((items) => items.length === 0 || items[items.length - 1] <= val)
      for (const items of itemsGroups) {
        dp[i].push([...items, val])
      }
    }
  }
  return dp[target]
}

其他思路

  • 上述动态规划有个缺点，不能从容应对同一数字选取次数受限的情况
  • 可以使用递归，传递游标位置解决这一问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var combinationSum = function (candidates, target) {
  candidates = candidates.sort((a, b) => a - b)
  const result = []
  const searchTree = (startIndex, curVals, remainVal) => {
    if (remainVal === 0) {
      result.push(curVals)
      return
    }
    if (startIndex >= candidates.length || remainVal < 0) {
      return
    }
    searchTree(startIndex, [...curVals, candidates[startIndex]], remainVal - candidates[startIndex])
    searchTree(startIndex + 1, curVals, remainVal)
  }
  searchTree(0, [], target)
  return result
}