Combination

46 Combination

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 List<List<Integer>> combinationSum(int[] num, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(num);
    dfs(num, ans, new ArrayList<Integer>(), 0, target);
    return ans;
}
private void dfs(int[] num, 
                List<List<Integer>> ans,
                List<Integer> list,
                int start,
                int remain
                ){
    if (remain < 0){
        return;
    }else if(remain == 0){
        ans.add(new ArrayList<>(list));
    }else{
        for (int i=start; i<num.length; i++){
            list.add(num[i]);
            dfs(num, ans, list, i, remain-num[i]);
            list.remove(list.size()-1);
        }
    }
}

47 Combination 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

• If condition skip duplicate

• dfs(...i+1...)

public List<List<Integer>> combinationSum2(int[] num, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    Arrays.sort(num);
    dfs(num, ans, new ArrayList<Integer>(), 0, target);
    return ans;
}

private void dfs(int[] num, 
                List<List<Integer>> ans,
                List<Integer> list,
                int start,
                int remain
                ){
    if (remain < 0){
        return;
    }else if(remain == 0){
        ans.add(new ArrayList<>(list));
    }else{
        for (int i=start; i<num.length; i++){
            if (i > start && num[i] == num[i-1]) continue; //skip duplicate
            list.add(num[i]);
            dfs(num, ans, list, i+1, remain-num[i]);
            list.remove(list.size()-1);
        }
    }
}