LeetCode - Combination Sum II

 Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(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+1, 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>> combinationSum2(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++) {
                    if (i != idx && candidates[i] == candidates[i - 1]) continue;
                    List<Integer> newList = new ArrayList<Integer>(list);
                    newList.add(candidates[i]);
                    stk1.push(newList);
                    stk2.push(candidates[i] + sum);
                    stk3.push(i + 1);
                }
            }
        }
        return res;
    }

}