Lintcode - Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations inC_where the candidate numbers sums toT_.

The same repeated number may be chosen from _C _unlimited number of times.

Example

Given candidate set[2,3,6,7]and target7, a solution set is:

[7]
[2, 2, 3]

Analysis: this problem is very similar compared to Combination Sum II. Except that the elements in the set can be used unlimited number of times to form a solution set. The solution is not to increment the index when doing the recursion.

   public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (candidates.length == 0){
            return result;
        }

        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<>();
        helper(path, result, 0, target, candidates);

        return result;
    }

    public void helper(List<Integer> path, List<List<Integer>> result, int index, int target, int[] candidates){
        if (target == 0){
            result.add(new ArrayList<Integer>(path));
            return;
        }

        for (int i = index; i < candidates.length; i++){
            if (i != index && candidates[i] == candidates[i-1]){
                continue;
            }

            if (candidates[i] > target){
                return;
            }


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