day-49.md

39.组合总和

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

题目描述

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

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

说明：

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

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]


提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

因为题目是求“所有可能的组合”，所以很自然想到了递归。感觉一提到组合我的第一反应就是，“对于每个元素，都有选与不选两种选择”，对每个元素分别作出选择后我们就得到了其中一个组合。

• 首先我们需要一个篮子来存放当前组合的元素，
• 然后，如果当前数字大于 target，那就直接跳过不考虑。
• 如果当前数字不大于 target：
  • 选：我们就把当前数字放篮子里，然后对后面的数字进行递归(注意：因为允许重复选择，所以“后面的数字”也包括当前数字)
  • 不选：把数字从篮子里拿出来(回溯)，然后对后面的数字进行递归(不包括当前数字)
• 递归出口：如果篮子里的数字和大于 target 了，那我们就把这个篮子扔掉不管(剪枝)；如果刚好等于 target，那就把篮子加到要返回的结果中，然后结束递归。

复杂度分析

• 时间复杂度：时间复杂度我就从 n 叉树的角度来想吧，也不知道对不对，$O(len(candidates)^{target/min(candidates)})$。
• 空间复杂度：调用栈的空间我感觉是 $O(target/min(candidates))$，一个组合最长的情况就是所有元素都是 min(candidate)，所以返回结果的空间应该是......不会算了...

代码

JavaScript Code

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    const dfs = (candidates, ans, remain, cur) => {
        if (remain < 0) return

        if (remain === 0) {
            res.push(ans)
            return
        }

        while (cur < candidates.length) {
            if (candidates[cur] <= remain) {
                ans.push(candidates[cur])
                dfs(candidates, [...ans], remain - candidates[cur], cur)
                ans.pop()
            }
            cur++
        }
    }

    const res = []
    dfs(candidates, [], target, 0)
    return res
}