39. 组合总和（难度：中等）

题目链接：https://leetcode-cn.com/problems/combination-sum/

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

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都是独一无二的。
• 1 <= target <= 500

解法一：回溯法+剪枝

回溯过程：

利用回溯法的思想，因为题目的要求是从candidates数组中找出可重复的几个数，然后让他们的和相加为target 。我们可以将问题一步一步分解为子问题，挨个遍历这个candidates数组，先选择一个数字candidates[i]，让target 减去t，然后再在candidates数组中找出可以相加等于target -candidates[i]的数，然后重复…… 直到target为0，则我们找到了一种组合，如果在寻找过程中，target<0，说明此路不通，我们回溯到上一层，重新选择数字。

剪枝：

我们在回溯的过程中，如何可以剪去一下分支的话，可以大大提高效率，可以剪枝的几种情况：

• 当我们遍历到的candidates[i]>target ，可以直接剪枝。

优化：

• 我们可以给candidates数组进行排序，让candidates[i]>target的适合，可以直接跳出这次循环，也就是包括他后面的元素的回溯都可以被剪枝。
• 我们遍历的适合，每次找到的新数字，一定比上一个大，那么我们拿到的就是一个递增的数组，这样就可以避免重复的结果集。

class Solution {
        public static List> combinationSum(int[] candidates, int target) {
        List> result = new ArrayList<>();
        getResult(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private static void getResult(List> result, List cur, int candidates[], int target, int start) {
        if (target == 0) {
            result.add(new ArrayList<>(cur));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (target < candidates[i])
                continue;
            cur.add(candidates[i]);
            getResult(result, cur, candidates, target - candidates[i], i);

            cur.remove(cur.size() - 1);
        }
    }
}

image.png