## Algorithm

Problem Name: 39. Combination Sum

Given an array of distinct integers `candidates` and a target integer `target`, return a list of all unique combinations of `candidates` where the chosen numbers sum to `target`. You may return the combinations in any order.

The same number may be chosen from `candidates` an unlimited number of times. Two combinations are unique if the

of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to `target` is less than `150` combinations for the given input.

Example 1:

```Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
```

Example 2:

```Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
```

Example 3:

```Input: candidates = [2], target = 1
Output: []
```

Constraints:

• `1 <= candidates.length <= 30`
• `2 <= candidates[i] <= 40`
• All elements of `candidates` are distinct.
• `1 <= target <= 40`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void bt(int *cand, int candsz, int target, int start, int dep, int **stack, int *spsz, int ***result, int **col, int *sz, int *ret) {
int i, j, *buff;
for (i = start; i  <  candsz; i ++) {
if (dep == *spsz) {
*spsz = (*spsz) * 2;
*stack = realloc(*stack, (*spsz) * sizeof(int));
//assert(*stack);
}
(*stack)[dep] = cand[i];

if (cand[i]  <  target) {
bt(cand, candsz, target - cand[i], i, dep + 1, stack, spsz, result, col, sz, ret);
} else if (cand[i] == target) {
// found it
buff = malloc((dep + 1) * sizeof(int));
//assert(buff);
memcpy(buff, *stack, (dep + 1) * sizeof(int));
if (*ret == *sz) {
*sz = (*sz) * 2;
*result = realloc(*result, (*sz) * sizeof(int *));
*col = realloc(*col, (*sz) * sizeof(int));
//assert(*result && *col);
}
(*result)[*ret] = buff;
(*col)[*ret] = dep + 1;
(*ret) += 1;
}
}
}

int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) {
int **result;
int sz = 100;
int *stack, spsz = 10;

result = malloc(sz * sizeof(int *));
*columnSizes = malloc(sz * sizeof(int));
stack = malloc(spsz * sizeof(int));
//assert(result && *columnSizes && stacksz);

*returnSize = 0;

bt(candidates, candidatesSize, target, 0, 0, &stack, &spsz, &result, columnSizes, &sz, returnSize);

if (*returnSize == 0) {
free(result);
free(*columnSizes);
*columnSizes = NULL;
result = NULL;
}
free(stack);

return result;
}
``````
Copy The Code &

Input

cmd
candidates = [2,3,6,7], target = 7

Output

cmd
[[2,2,3],[7]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector < vector<int>>res;
vector<int>comb;
backtrack(res, candidates, 0, 0, target, comb);
return res;
}

void backtrack(vector < vector<int>>& res, vector<int>& candidates, int pos, int sum, int target, vector<int>& comb){
if(sum > target || pos == candidates.size()) return;
if(sum == target){
res.push_back(comb);
return;
}
backtrack(res, candidates, pos + 1, sum, target, comb);
comb.push_back(candidates[pos]);
backtrack(res, candidates, pos, sum + candidates[pos], target, comb);
comb.pop_back();
}
};
``````
Copy The Code &

Input

cmd
candidates = [2,3,5], target = 8

Output

cmd
[[2,2,2,2],[2,3,3],[3,5]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
helper(candidates, 0, target, new ArrayList<>(), result);
return result;
}

private void helper(int[] candidates, int idx, int target, List < Integer> currCombination,
List(currCombination));
}
if (target > 0 && idx < candidates.length) {
for (int i = idx; i  <  candidates.length; i++) {
helper(candidates, i, target - candidates[i], currCombination, result);
currCombination.remove(currCombination.size() - 1);
}
}
}
}
``````
Copy The Code &

Input

cmd
candidates = [2], target = 1

Output

cmd
[]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const combinationSum = 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++) {
combination.push(candidates[i]);
bt(candidates, target - candidates[i], res, combination, i);
combination.pop();
}
}
``````
Copy The Code &

Input

cmd
candidates = [2,3,6,7], target = 7

Output

cmd
[[2,2,3],[7]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def combinationSum(self, c, t):
res, stack, n = [], [(0, [], 0)], len(c)
while stack:
sm, tmp, r = stack.pop()
for i in range(r, n):
if sm + c[i] < t:
stack.append((sm + c[i], tmp + [c[i]], i))
elif sm + c[i] == t:
res.append(tmp + [c[i]])
return res
``````
Copy The Code &

Input

cmd
candidates = [2,3,5], target = 8

Output

cmd
[[2,2,2,2],[2,3,3],[3,5]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _039_CombinationSum
{
public IList < IList<int>> CombinationSum(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; }

if (candidates[i] == gap)
{
result.Add(new List < int>(tempResult));
}
else
{
DeepFirstSearch(candidates, gap - candidates[i], i, tempResult, result);
}
tempResult.RemoveAt(tempResult.Count - 1);
}
}
}
}
``````
Copy The Code &

Input

cmd
candidates = [2], target = 1

Output

cmd
[]