LeetCode/39. 组合总和

39. 组合总和

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题我们还是依靠全排列的回溯思想，让我们在全排列的基础上修改此题。很直观的想法，就是该数组元素之和要等于target，那么我们可以设置一个变量count，每次回溯往track中添加元素后和target比较大小，如果相等则该track就是我们想要的结果，将track加入result中，如果target小于count，显然此时已经没有意义了，我们直接return。

具体代码如下：

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

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

    void backtrack(int[] candidates, int target, int start, int count, LinkedList<Integer> track) {
        //触发结束条件
        if (target == count) {
            result.add(new LinkedList<>(track));
            return;
        }
        //如果count超过target则直接返回，
        if (target < count) {
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            //将track中未出现的元素加入
            track.add(candidates[i]);
            backtrack(candidates, target, i, count + candidates[i], track);
            //剔除最后一个元素，尝试下一个不同的元素
            track.removeLast();
        }
    }
}

既然正向加可以，那么自然而然就会想到逆向减也是可行的，并且如果是逆向减的话还不需要设置count变量，节省了空间。我们直接将target - candidates[i]传入backtrack方法，如果target == 0时说明数组之和等于target，同样，如果target < 0证明值超了，这时直接return即可。

具体代码如下：

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

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

    void backtrack(int[] candidates, int target, int start, LinkedList<Integer> track) {
        //触发结束条件
        if (target == 0) {
            result.add(new LinkedList<>(track));
            return;
        }
        if (target < 0) {
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            //将track中未出现的元素加入
            track.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, track);
            //剔除最后一个元素，尝试下一个不同的元素
            track.removeLast();
        }
    }
}