夯实算法-组合总和

题目：LeetCode

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 **不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入： candidates = [2,3,6,7], target = 7
输出： [[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

解题思路

根据题意可以使用回溯算法，每次从candidates中选择一个元素，然后分两条路递归进行，一是把这个元素加入到组合之中，一个不加入，直接跳到下一个元素。 直到子集合中的元素之和等于目标target时，就找到了一个符合题意的子集。

另外，运用逆向思维，不要在搜索过程中做累加，而是做减法，当target减小到０的时候，就找到一组符合题意的组合。

当target小于零时，说明这条路径已经不可能找出符合题意的组合，可以直接pass掉，或者已经没有了可选的剩余元素(index >= length时)时，也是不可能选择出符合题意的组合，也排除掉。

代码实现

private List < List < Integer >> result = new LinkedList < > ();
private LinkedList < Integer > combination = new LinkedList < > ();

public List < List < Integer >> combinationSum(int[] candidates, int target) {
    result.clear();
    combination.clear();

    combine(candidates, target, 0);
    return result;
}

private void combine(int[] nums, int target, int index) {
    // 找到了一个符合要求的组合
    if (target == 0) {
        result.add(new LinkedList < > (combination));
    } else if (target > 0 && index < nums.length) {
        // 剪枝１：当target<0，说明此路径找不到符合要求的组合了
        // 剪枝２：当index到底了，说明没有更多的元素可供选择了，也就找不到符合要求的组合了

        // 当前元素不加入组合，直接跳过到下一个元素
        combine(nums, target, index + 1);
        // 当前元素加入组合
        combination.add(nums[index]);
        // 还需要把当前元素从目标target中扣除，并且因为元素可重复，所以仍继续尝试当前元素
        combine(nums, target - nums[index], index);
        // 回溯，从组合中删除。因为并未对target产生实质影响，所以target的扣除不用做额外的回溯
        combination.removeLast();
    }
}

复杂度分析

• 空间复杂度：O(1)O(1)O(1)
• 时间复杂度：O(n2)O(n^2)O(n2)