题目描述

给定一个无重复元素的数组 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]
]

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

解法1

在上一篇文章“代码模版-排列与组合”我们介绍了排列与组合的实现方法，在这道题中，我们将会在组合算法上进行一些修改来解这道题目。我们先观察下组合算法的实现。

private void combination(int[] arr, int depth, int start, int[] curr, List<int[]> result) {
        if (depth == curr.length) {
            result.add(Arrays.copyOf(curr, curr.length));
            return;
        }
        for (int i = start; i < arr.length; i++) {
            curr[depth] = arr[i];
            combination(arr, depth + 1, i + 1, curr, result);
        }
}

在这道题目中，要求数字可以重复选取，但是上面的代码每次都会选取新的一个数字。我们将递归调用combination(arr, depth + 1, i + 1, curr, result)改成combination(arr, depth + 1, i, curr, result)，就可以实现选取重复的数字。此外，我们将对combination添加一个新的参数target，表示距离目标还相差多少数值。如果在递归函数的入口发现target为0，我们就找到了一组可行的组合。

全部代码如下：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> curr = new ArrayList<>(candidates.length);

        combination(candidates, 0, curr, ans, target);

        return ans;
    }

    private void combination(int[] arr, int start, List<Integer> curr, List<List<Integer>> ans, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            // 当前数字必须小于等于target，否则target扣完就为负数，永远不可能到0
            if (target >= arr[i]) {
                curr.add(arr[i]);
                combination(arr, i, curr, ans, target - arr[i]);
                curr.remove(curr.size() - 1);
            }
        }
    }
}

解法1优化

解法1还是有优化空间的，我们可以剪枝来减少不必要的计算。我们可以对输入数组candidates按照从小到大顺序排序，当选取的数字之和大于target，我们就没必要继续往下计算了（因为candidates已经排序了，之后选取的数字只会更大）。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> curr = new ArrayList<>(candidates.length);
        // 从小到大排序
        Arrays.sort(candidates);
        combination(candidates, 0, curr, ans, target);
        return ans;
    }

    private void combination(int[] arr, int start, List<Integer> curr, List<List<Integer>> ans, int target) {
        if (target == 0) {
            ans.add(new ArrayList<>(curr));
            return;
        }

        for (int i = start; i < arr.length; i++) {
            // 剪枝
            if (target < arr[i]) break;
            curr.add(arr[i]);
            combination(arr, i, curr, ans, target - arr[i]);
            curr.remove(curr.size() - 1);
        }
    }
}