39.组合总和

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

• 39.组合总和

  • 题目描述

  • 方法 1：回溯

    • 思路

    • 复杂度分析

    • 代码

题目描述

给定一个无重复元素的数组 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：回溯

思路

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

• 首先我们需要一个篮子来存放当前组合的元素，

• 然后，如果当前数字大于 target，那就直接跳过不考虑。

• 如果当前数字不大于 target：

  • 选：我们就把当前数字放篮子里，然后对后面的数字进行递归(注意：因为允许重复选择，所以“后面的数字”也包括当前数字)

  • 不选：把数字从篮子里拿出来(回溯)，然后对后面的数字进行递归(不包括当前数字)

• 递归出口：如果篮子里的数字和大于 target 了，那我们就把这个篮子扔掉不管(剪枝)；如果刚好等于 target，那就把篮子加到要返回的结果中，然后结束递归。

复杂度分析

力扣官方的分析：

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

• 空间复杂度：$O(target)$。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 $O(target)$ 层。

代码

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;
};

JavaScript Code

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    candidates.sort((a, b) => a - b);
    const res = [];
    dfs(candidates, 0, target);
    return res;

    // ******************************************
    function dfs(arr, cur, target, tempArr = [], total = 0) {
        if (total > target) return;

        if (total === target) {
            res.push([...tempArr]);
            return;
        }

        // 因为数字可以重复选择，所以 i 从 cur 开始
        for (let i = cur; i < arr.length; i++) {
            // 剪枝
            if (total + arr[cur] > target) break;

            // 选当前数字
            tempArr.push(arr[i]);

            // 递归决定选不选后面的数字
            dfs(arr, i, target, tempArr, total + arr[i]);

            // 不选当前数字
            tempArr.pop();
        }
    }
};