Jan 17 - Combination Sum II; Backtracking; Array;

public class Solution {
    Set<List<Integer>> set = new HashSet<>();
    boolean flag = false;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int len = candidates.length;
        int[] count = new int[len];
        List<List<Integer>> listResult = new ArrayList<>();
        if(len == 0) return listResult;
        Arrays.sort(candidates);
        //int i = 0;
        traverseArray(candidates, 0, target, count);
        listResult = new ArrayList<>(set);
        /*
        while(i < len && candidates[i] <= target){
            traverseArray(candidates, i, target, count);
            while(i < (len-1) && candidates[i] == candidates[i+1]) i++;
            i++;
        }
        */
        return listResult;
    }
    
    public void traverseArray(int[] candidates, int i, int target, int[] count){
        if(target == 0){
            flag = true;
            return;
        }
        int k = i;
        while(k < candidates.length && candidates[k] <= target){
            count[k]++;
            traverseArray(candidates, k+1, target-candidates[k], count);
            if(flag){
                List<Integer> list = new ArrayList<>();
                for(int m = 0; m <= k; m++){
                    if(count[m] > 0) list.add(candidates[m]);
                }
                set.add(list);
                flag = false;
                //while(k < (candidates.length-1) && candidates[k] == candidates[k+1]) k++;
            }
            count[k] = 0;
            k++;
        }
    }
}