LeetCode - Combination Sum

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

The same repeated number may be chosen from C unlimited number of times.

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(candidates==null) {
            return null;
        }
        Arrays.sort(candidates);
        recursive(candidates, 0, new ArrayList<Integer>(), 0, target, ret);
        return ret;
    }
 
    public void recursive(int[] candidates, int start, ArrayList<Integer> lst, int sum, int target, ArrayList<ArrayList<Integer>> ret)  {
        if(sum==target) {
            ArrayList<Integer> re = new ArrayList<Integer>(lst);
            ret.add(re);
        } else if(sum>target) {
            return;
        } else {
            for(int i=start;i<candidates.length;i++) {
                sum += candidates[i];
                lst.add(candidates[i]);
                recursive(candidates, i, lst, sum, target, ret);
                sum -= candidates[i];
                lst.remove(lst.size()-1);
                while(i<candidates.length-1 && candidates[i]==candidates[i+1]) {
                i++;
                }
            }
        }
    }
}


public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return ret;
        }
        Arrays.sort(candidates);
        helper(candidates, 0, target, 0, new ArrayList<Integer>(), ret);
        return ret;
    }
 
    private void helper(int[] candidates, int cur, int target, int curSum, List<Integer> curList, List<List<Integer>> ret) {
        if (curSum == target) {
            List<Integer> newList = new ArrayList<Integer>(curList);
            ret.add(newList);
        } else if (curSum < target && curSum + candidates[cur] <= target) {
            for (int i = cur; i < candidates.length; i++) {
                if (i > 0 && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                curList.add(candidates[i]);
                helper(candidates, i, target, curSum + candidates[i], curList, ret);
                curList.remove(curList.size() - 1);
            }
        }
    }
}

===========

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Stack<List<Integer>> stk1 = new Stack<>();
        Stack<Integer> stk2 = new Stack<>();
        Stack<Integer> stk3 = new Stack<>();
       
        stk1.push(new ArrayList<Integer>());
        stk2.push(0);
        stk3.push(0);
        Arrays.sort(candidates);
        while (!stk1.isEmpty()) {
            List<Integer> list = stk1.pop();
            int sum = stk2.pop();
            int idx = stk3.pop();
            if (sum == target) {
                res.add(new ArrayList<Integer>(list));
            } else if (sum < target) {
                for (int i = idx; i < candidates.length; i++) {
                    List<Integer> newList = new ArrayList<Integer>(list);
                    newList.add(candidates[i]);
                    stk1.push(newList);
                    stk2.push(candidates[i] + sum);
                    stk3.push(i);
                }
            }
        }
        return res;
    }
}