## Algorithm

Problem Name: 40. 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 <= 100`
• `1 <= candidates[i] <= 50`
• `1 <= 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
return;
}
for (i = start; i  <  sz; i ++) {
if (i > start && cand[i] == cand[i - 1]) continue;  // skip duplicated
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;
}
``````
Copy The Code &

Input

cmd
candidates = [10,1,2,7,6,1,5], target = 8

Output

cmd
[ [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(>;
}
}
};
``````
Copy The Code &

Input

cmd
candidates = [2,5,2,1,2], target = 5

Output

cmd
[ [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) {
}
return;
}
for (int i = idx; i  <  candidates.length; i++) {
if (i > idx && candidates[i] == candidates[i - 1]) {
continue;
}
helper(candidates, target - candidates[i], result, currCombination, i + 1);
currCombination.remove(currCombination.size() - 1);
}
}
}
``````
Copy The Code &

Input

cmd
candidates = [10,1,2,7,6,1,5], target = 8

Output

cmd
[ [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();
}
}
``````
Copy The Code &

Input

cmd
candidates = [2,5,2,1,2], target = 5

Output

cmd
[ [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)
``````
Copy The Code &

Input

cmd
candidates = [10,1,2,7,6,1,5], target = 8

Output

cmd
[ [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];

if (candidates[i] == gap)
{
}
else
{
DeepFirstSearch(candidates, gap - candidates[i], i + 1, tempResult, result);
}
tempResult.RemoveAt(tempResult.Count - 1);
}
}
}
}
``````
Copy The Code &

Input

cmd
candidates = [2,5,2,1,2], target = 5

Output

cmd
[ [1,2,2], [5] ]