Algorithm
Problem Name: 40. Combination Sum II
Problem Link: https://leetcode.com/problems/combination-sum-ii/
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.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ]
Constraints:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int **p;
int *col;
int sz;
int n;
} res_t;
typedef struct {
int *b;
int sz;
} buff_t;
void add2buff(buff_t *buff, int d, int k) {
if (buff->sz == 0) {
buff->sz = 10;
buff->b = malloc(buff->sz * sizeof(int));
//assert(buff->b);
} else if (buff->sz == d) {
buff->sz *= 2;
buff->b = realloc(buff->b, buff->sz * sizeof(int));
//assert(buff->b);
}
buff->b[d] = k;
}
void add2res(res_t *res, int *b, int d) {
int *tmp = malloc(d * sizeof(int));
//assert(tmp);
memcpy(tmp, b, d * sizeof(int));
if (res->sz == 0) {
res->sz = 10;
res->p = malloc(res->sz * sizeof(int *));
res->col = malloc(res->sz * sizeof(int));
//assert(res->p && res->col);
} else if (res->sz == res->n) {
res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(int *));
res->col = realloc(res->col, res->sz * sizeof(int));
//assert(res->p && res->col);
}
res->p[res->n] = tmp;
res->col[res->n] = d;
res->n ++;
}
void bt(int *cand, int sz, int target, int start, int d, buff_t *buff, res_t *res) {
int i;
if (target < 0) return; // no solution
if (target == 0) { // found it
add2res(res, buff->b, d);
return;
}
for (i = start; i < sz; i ++) {
if (i > start && cand[i] == cand[i - 1]) continue; // skip duplicated
add2buff(buff, d, cand[i]);
bt(cand, sz, target - cand[i], i + 1, d + 1, buff, res);
}
}
int cmp(const void *a, const void *b) {
int x = *(int *)a;
int y = *(int *)b;
return (x < y) ? -1 :
(x > y) ? 1 : 0;
}
int** combinationSum2(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) {
res_t res = { 0 };
buff_t buff = { 0 };
if (candidatesSize) {
qsort(candidates, candidatesSize, sizeof(int), cmp);
bt(candidates, candidatesSize, target, 0, 0, &buff, &res);
if (buff.b) free(buff.b);
}
*returnSize = res.n;
*columnSizes = res.col;
return res.p;
}
Input
candidates = [10,1,2,7,6,1,5], target = 8
Output
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector < vector<int>>res;
vector<int>path;
DFS(res, candidates, 0, 0, target, path);
return res;
}
void DFS(vector < vector<int>>& res, vector<int>& candidates, int pos, int sum, int target, vector<int>& path){
if(sum >= target){
if(sum == target) res.push_back(path);
return;
}
for(int i = pos; i < candidates.size(); i++){
if(i != pos && candidates[i] == candidates[i - 1]) continue;
path.push_back(candidates[i]);
DFS(res, candidates, i + 1, sum + candidates[i], target, path);
path.pop_back(>;
}
}
};
Input
candidates = [2,5,2,1,2], target = 5
Output
[
[1,2,2],
[5]
]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
Arrays.sort(candidates);
helper(candidates, target, result, new ArrayList < >(), 0);
return result;
}
private void helper(int[] candidates, int target, List < List currCombination, int idx) {
if (target <= 0) {
if (target == 0) {
result.add(new ArrayList<>(currCombination));
}
return;
}
for (int i = idx; i < candidates.length; i++) {
if (i > idx && candidates[i] == candidates[i - 1]) {
continue;
}
currCombination.add(candidates[i]);
helper(candidates, target - candidates[i], result, currCombination, i + 1);
currCombination.remove(currCombination.size() - 1);
}
}
}
Input
candidates = [10,1,2,7,6,1,5], target = 8
Output
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const combinationSum2 = function(candidates, target) {
candidates.sort((a, b) => a - b);
const res = [];
bt(candidates, target, res, [], 0);
return res;
};
function bt(candidates, target, res, combination, start) {
if (target === 0) {
res.push(combination.slice(0));
return;
}
for (let i = start; i < candidates.length && target >= candidates[i]; i++) {
if (i > 0 && candidates[i] === candidates[i - 1] && i > start) continue;
combination.push(candidates[i]);
bt(candidates, target - candidates[i], res, combination, i + 1);
combination.pop();
}
}
Input
candidates = [2,5,2,1,2], target = 5
Output
[
[1,2,2],
[5]
]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def combinationSum2(self, candidates, target):
res = []
self.dfs(sorted(candidates), target, 0, [], res)
return res
def dfs(self, nums, target, index, path, res):
if target < 0:
return
if target == 0 and path not in res:
res.append(path)
return
for i in range(index, len(nums)):
if i>1 and nums[i] == nums[i-1]:
continue
self.dfs(nums[:i] + nums[i+1:], target-nums[i], i, path+[nums[i]], res)
Input
candidates = [10,1,2,7,6,1,5], target = 8
Output
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _040_CombinationSum2
{
public IList < IList<int>> CombinationSum2(int[] candidates, int target)
{
Array.Sort(candidates);
var result = new List < IList<int>>();
DeepFirstSearch(candidates, target, 0, new List < int>(), result);
return result;
}
void DeepFirstSearch(int[] candidates, int gap, int startIndex, IList < int> tempResult, IList gap) { return; }
previous = candidates[i];
tempResult.Add(candidates[i]);
if (candidates[i] == gap)
{
result.Add(new List < int>(tempResult));
}
else
{
DeepFirstSearch(candidates, gap - candidates[i], i + 1, tempResult, result);
}
tempResult.RemoveAt(tempResult.Count - 1);
}
}
}
}
Input
candidates = [2,5,2,1,2], target = 5
Output
[
[1,2,2],
[5]
]