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);
}
}
}