代码随想录算法训练营第十九天｜LeetCode 39. 组合总和、 40. 组合总和II

回溯算法 的第二天！

题目链接：39. 组合总和

状态：不了解回溯算法，所以前几题都是直接看解析做的，先体验一下。

本题与昨天的题的区别在于 本题没有数量的要求，可以无限重复。限制的条件在于总和。所以树形结构如下：

组合总和树形结构图

递归的终止条件很清晰了：sum >= target。而在sum等于target的时候，就需要收集结果了。
单层搜索的逻辑：依然是从startIndex开始，搜索candidates集合，区别就在于本题元素可重复选择，所以i不用加一了。
剪枝优化：如果下一层的sum(就是本层的sum+candidates[i])已经大于target，就可以结束本轮for循环的遍历了。剪枝代码如下：

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++)

完整代码如下：

class Solution { // Java
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }
}

复杂度分析：
时间复杂度：O(k * 2^n). 最坏情况下，递归树的每个节点都会有两个分支（即选择或不选择当前元素），所以递归树的大小为O(2^n), 其中n是candidate数组的长度；而每次找到一个满足条件的组合时，都需要花费O(k)的时间将其复制到结果列表res中，其中k是组合的平均长度。
空间复杂度：O(k). 递归调用最大深度为k，临时路径path列表的最大长度也是k。