39. 组合总和（高频题）

39. 组合总和

• 解题思路
• 代码

解题思路

看到是组合问题，直接用回溯法，然后再剪枝避免出现重复组合就行了，直接套回溯法模板。

代码

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        LinkedList<Integer> track = new LinkedList<>();
        Arrays.sort(candidates);
        backtrack(candidates, 0, target, track);
        return res;
    }

    private void backtrack(int[] candidates, int start, int target, LinkedList<Integer> track) {
        if (target < 0) return;
        if (target == 0) {
            res.add(new LinkedList<>(track));
            return;
        }
        //这里从start开始是为了去重
        for (int i = start; i < candidates.length; i++) {
            /* 这就是排序的好处，可以直接这样剪枝，否则还得遍历
                比如[1,2,3,4,5] target=3;那么你要和为3，单个元素必须小于3.所以大于三
                的直接不用遍历了，肯定是不满足条件的
            */
            if (target < candidates[i]) break;
            track.add(candidates[i]);
            backtrack(candidates, i, target - candidates[i], track);
            track.removeLast();
        }
    }
}