Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.

Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

Example 1: Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2: Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]

每次往combination里放一个数，然后target变为target-该数
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();

        if(candidates == null || candidates.length == 0) return res;

        Arrays.sort(candidates);

        List<Integer> combination = new ArrayList<>();
        helper(res, combination, candidates, target, 0);
        return res;
    }

    private void helper(List<List<Integer>> res, List<Integer> combination, int[] candidates, int target, int start) {
        if(target == 0) {
            res.add(new ArrayList<>(combination));
            return;
        }

        for(int i = start; i < candidates.length; i++) {
            if(target < 0) break;

            combination.add(candidates[i]);
            helper(res, combination, candidates, target - candidates[i], i);
            combination.remove(combination.size() - 1);
        }
    }
}