组合总和

---

题目叙述：

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

解题思路：

先将给出来的nums数组进行排序，从第i个开始将后续的添加进去，后续递归调用，将help也要传进递归调用中，如果和比target大，如果等于target将结果加进结果集中，一次递归结束后将当前数的将加入的数移出来。时间复杂度O(n^2)

代码实现：

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

    private void backtrack(List<List<Integer>> res, List<Integer> help, int [] nums, int remain, int start){
        if(remain < 0) return;
        else if(remain == 0) res.add(new ArrayList<>(help));
        else{ 
            for(int i = start; i < nums.length; i++){
                help.add(nums[i]);
                backtrack(res, help, nums, remain - nums[i], i); 
                help.remove(help.size() - 1);
            }
        }
    }
}