39. Combination Sum

给一组候选数字（C）（没有重复）并给一个目标数字（T），找出 C 中所有唯一的组合使得它们的和为 T。

可以从 C 无限次数中选择相同的数字。

说明：

所有数字（包括目标）都是正整数。
解集合中没有相同组合。

https://leetcode.com/problems/combination-sum/description/

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    ArrayList<List<Integer>> res = new ArrayList<>();
    if (candidates == null || candidates.length == 0) {
        return res;
    }
    // Arrays.sort(candidates);
    backtracking(target, 0, candidates, new ArrayList<Integer>(), res);
    
    return res;
}

private void backtracking(int target, int index, int[] nums, ArrayList<Integer> path, ArrayList<List<Integer>> res) {
    if (target == 0) {
        res.add(new ArrayList<Integer>(path));
        return;
    }
    if (target < 0 || index >= nums.length) {
        return;
    }
    
    for (int i = index; i < nums.length; i++) {
        path.add(nums[i]);
        // item 可以重复使用，故 next index 为 i
        backtracking(target - nums[i], i, nums, path, res);
        path.remove(path.size() - 1);
    }
}

follow up:
https://leetcode.com/problems/combination-sum-ii/description/
给定候选号码数组 (C) 和目标总和数 (T)，找出 C 中候选号码总和为 T 的所有唯一组合。

C 中的每个数字只能在组合中使用一次。

注意:

所有数字（包括目标）都是正整数。
解决方案集不能包含重复的组合。

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    ArrayList<List<Integer>> res = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return res;
    }
    
    Arrays.sort(nums);
    backtracking(target, 0, nums, new ArrayList<Integer>(), res);
    
    return res;
}

private void backtracking(int target, int index, int[] nums, ArrayList<Integer> path, ArrayList<List<Integer>> res) {
    if (target == 0) {
        res.add(new ArrayList<Integer>(path));
        return;
    }
    if (target < 0 || index >= nums.length) {
        return;
    }
    for (int i = index; i < nums.length; i++) {
        
        // 该 for 循环，是对 current path next item 的尝试；
        // 当 i>index 且nums[i] == nums[i - 1], 
        // 说明这个 item 对 current path next item 的尝试已经在之前完成过了，
        // 就不需要，也不应该再尝试了。
        if (i > index && nums[i] == nums[i - 1]) {
            continue;
        }

        path.add(nums[i]);
        backtracking(target - nums[i], i + 1, nums, path, res);
        path.remove(path.size() - 1);
    }
}