39. Combination Sum

题目描述和难度

题目描述：给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。
题目难度：中等。
英文网址：39. Combination Sum 。
中文网址：39. 组合总和。

思路分析

求解关键：注意分析题意，找到可以减少判断的条件：（1）这道题猛地一看好像跟前面的问题搭不上关系，因为题目中说“candidates 中的数字可以无限制重复被选取”；
（2）但其实仔细想想就会发现，我们每次取数字的时候，还从原点开始取就行了呀，是不是很酷；
（3）为了达到提前判断循环结束的效果，我们可以先对数组排个序，如果起点数字比剩下的和还要大，后面的循环就没有必要进行下去了。此时，我们在 for 循环里加判断，尽量减少了系统栈的调用深度。

参考解答

参考解答1（没有做优化剪枝的版本）

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private int[] candidates;
    private int len;

    // residue 定义为剩余，这个剩余一开始等于 target，在递归中，它的值会越来越小
    // 因为题目中说了"所有数字（包括 target）都是正整数"。
    private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
        // 因为可以无限选取，所以 residue 只能小于 0 或者等于 0
        if (residue < 0) {
            return;
        }
        // 一定是剩下的那个数为 0 了，才表示我们所选的数字的和刚好等于 target
        if (residue == 0) {
            res.add(new ArrayList<>(pre));
            return;
        }
        for (int i = start; i < len; i++) {
            // 每个数有选择和不选择，因此尝试了一种解的可能以后要进行状态重置
            pre.add(candidates[i]);
            // 【关键】因为元素可以重复使用，这里递归传递下去的是 i 而不是 i + 1
            findCombinationSum(residue - candidates[i], i, pre);
            pre.pop();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        this.len = len;
        this.candidates = candidates;
        findCombinationSum(target, 0, new Stack<>());
        return res;
    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        Solution solution = new Solution();
        List<List<Integer>> combinationSum = solution.combinationSum(candidates, target);
        System.out.println(combinationSum);
    }
}

参考解答2（推荐）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution2 {

    private List<List<Integer>> res = new ArrayList<>();
    private int[] candidates;
    private int len;

    private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
        if (residue == 0) {
            res.add(new ArrayList<>(pre));
            return;
        }
        // 优化添加的代码2：在循环的时候做判断，尽量避免系统栈的深度
        // residue - candidates[i] 表示下一轮的剩余，如果下一轮的剩余都小于 0 ，就没有必要进行后面的循环了
        // 这一点基于原始数组是排序数组的前提，因为如果计算后面的剩余，只会越来越小
        for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
            pre.add(candidates[i]);
            // 【关键】因为元素可以重复使用，这里递归传递下去的是 i 而不是 i + 1
            findCombinationSum(residue - candidates[i], i, pre);
            pre.pop();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int len = candidates.length;
        if (len == 0) {
            return res;
        }
        // 优化添加的代码1：先对数组排序，可以提前终止判断
        Arrays.sort(candidates);
        this.len = len;
        this.candidates = candidates;
        findCombinationSum(target, 0, new Stack<>());
        return res;
    }
}