Java描述 LeetCode，39. Combination Sum 组合总和

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
All elements of candidates are distinct.
1 <= target <= 500

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

还是一道组合题目，在题解（精解）里面说的比较清楚了，这里给出我的代码和补充：

List> result = new ArrayList<>();
linkedList path = new linkedList<>();

public List> combinationSum(int[] candidates, int target) {
//        Arrays.sort(candidates);
    backTrack(candidates, target, 0);
    return result;
}

public void backTrack(int[] candidates, int target, int begin) {
    if (target == 0) {
        result.add(new ArrayList<>(path));
        return;
    }
    if (target < 0) {
        return;
    }
    for (int i = begin; i < candidates.length; i++) {
        // 重点理解这里剪枝，前提是候选数组已经有序，
        if (target - candidates[i] < 0) {
        	// 1.break;
            continue;
        }
        path.addLast(candidates[i]);
        backTrack(candidates, target - candidates[i], i);
        path.removeLast();
    }
}

两点想要说明的就是，

为什么要先排序才能用break，同时我也给出了不排序就得用continue的解法。试想一下，排序和不排序的区别就在于i之后的数字，不排序i之后还会出现比candidates[i]小的数字，所以不能一棍子打死，如果你看完了题解里面的精解，你会知道我在说什么。怎么做到不出现重复的情况（也就是组合相同，排列不同）？比如[2,2,3] [2,3,2] [3,2,2]这种？这边用了i=begin防止走“回头路”，比如2,3,5,target=7，选完3之后，第二轮不会再回过头来选2了！如果i=0从0开始的话，就会出现走“回头路”的现象。你细品。剪枝：习以为常了，做过几道或者，你把题解里面看明白 就也会了。