Combination Sum II Problem: Given a collection of candidate numbers (candidates
) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sum to target
.
Each number in candidates
may only be used once in the combination.
The solution set must not contain duplicate combinations.
Example :
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Table of Contents
Combination Sum II Problem Solution
Problem Solution In Python
def combinationSum2(self, nums, target):
def bt(tlist, start, target):
s = sum(tlist)
if s == target:
res.append(tlist[::])
return
if s > target:
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue
tlist.append(nums[i])
bt(tlist, i + 1, target)
tlist.pop()
nums.sort()
res = []
bt([], 0, target)
return res
Problem Solution In Java
class Solution {
HashSet<List<Integer>> set = new HashSet<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<Integer> tempList = new ArrayList<>();
backtrack(tempList,candidates,target,0);
List<List<Integer>> res = new ArrayList<>();
for(List<Integer> ls:set){
res.add(ls);
}
return res;
}
public void backtrack(List<Integer> tempList,int[] candidates,int needed_target,int start){
if(needed_target==0){
set.add(new ArrayList<>(tempList));
return;
}
for(int i=start;i<candidates.length;i++){
if(candidates[i]>needed_target) continue;
tempList.add(candidates[i]);
backtrack(tempList,candidates,needed_target-candidates[i],i+1);
tempList.remove(tempList.size()-1);
}
}
}
Problem Solution In C++
#define pb push_back
class Solution {
public:
vector<vector<int>> res;
void getlist(vector<int>& ar,int index,int target , vector<int>& s){
int sum = accumulate(s.begin(),s.end(),0);
if(sum == target){
res.pb(s);
return;
}
if(sum > target || ar.size() <= index){
return;
}
getlist(ar,index+1,target,s);
s.pb(ar[index]);
getlist(ar,index+1,target,s);
s.pop_back();
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> s;
getlist(candidates,0,target,s);
vector<vector<int>> ans;
set<vector<int>> st;
for(auto x : res){
vector<int> temp = x;
sort(temp.begin(),temp.end());
st.insert(temp);
}
for(auto x : st){
ans.pb(x);
}
return ans;
}
};
Problem Solution In C
void dfs(int* nums, int* colSizes, int numsSize, int target,
int** sols, int* sols_size, int* sol, int sol_size, int pointer) {
if(target < 0) return;
else if(target == 0) {
sols[*sols_size] = calloc(sol_size, sizeof(int));
for(int i = 0; i < sol_size; i++) sols[*sols_size][i] = sol[i];
colSizes[*sols_size] = sol_size;
(*sols_size)++;
}
else{
for(int i = pointer; i < numsSize; i++) {
if(nums[i] > target) return;
if(i != pointer && nums[i] == nums[i - 1]) continue;
sol[sol_size] = nums[i];
dfs(nums, colSizes, numsSize, target - nums[i],
sols, sols_size, sol, sol_size + 1, i + 1);
}
}
}
int comp(const void* v1, const void* v2) {
return (*(int*) v1) - (*(int*) v2);
}
int** combinationSum2(int* nums, int numsSize, int target, int** colSizes, int* returnSize) {
int** sols = calloc(500, sizeof(int*));
*colSizes = calloc(500, sizeof(int));
int* sol = calloc(500, sizeof(int));
qsort((void*) nums, numsSize, sizeof(int), comp);
dfs(nums, *colSizes, numsSize, target, sols, returnSize, sol, 0, 0);
return sols;
}