LeetCode.39. 组合总和

LeetCode.39. 组合总和

难度：medium

Java：

跳出的条件有两个，sum > target 和 sum == target；

本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？

举过例子，如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合

未剪枝：

class Solution {
    List> ans = new ArrayList>();
 
    List path = new ArrayList<>();
    int sum = 0;
    public List> combinationSum(int[] candidates, int target) {
 
        backTracking(candidates, target, 0);
        return ans;
    }
    // startIndex控制选取元素的范围，出现只是元素顺序不同的组合
    public void backTracking(int[] candidates, int target, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
 
        for (int i = startIndex; i < candidates.length; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            // startIndex = i，表明可以重复选取当前元素
            backTracking(candidates, target, i);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

 剪枝方法：

以及上面的版本一的代码大家可以看到，对于sum已经大于target的情况，其实是依然进入了下一层递归，只是下一层递归结束判断的时候，会判断sum > target的话就返回。

其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

class Solution {
    List> ans = new ArrayList>();
 
    List path = new ArrayList<>();
    int sum = 0;
    public List> combinationSum(int[] candidates, int target) {
        // 需要排序
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return ans;
    }
    // startIndex控制选取元素的范围，出现只是元素顺序不同的组合
    public void backTracking(int[] candidates, int target, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
 
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            // startIndex = i，表明可以重复选取当前元素
            backTracking(candidates, target, i);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

复杂度分析：

• 时间复杂度：O（S），其中 S 为所有可行解的长度之和。
• 空间复杂度：O（n），n为递归的深度