Algorithm
Problem Name: 39. Combination Sum
Problem Link: https://leetcode.com/problems/combination-sum/
of at least one of the chosen numbers is different.
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
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 <= 302 <= candidates[i] <= 40- All elements of
candidatesare 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;
}
Input
candidates = [2,3,6,7], target = 7
Output
[[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();
}
};
Input
candidates = [2,3,5], target = 8
Output
[[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++) {
currCombination.add(candidates[i]);
helper(candidates, i, target - candidates[i], currCombination, result);
currCombination.remove(currCombination.size() - 1);
}
}
}
}
Input
candidates = [2], target = 1
Output
[]
#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();
}
}
Input
candidates = [2,3,6,7], target = 7
Output
[[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
Input
candidates = [2,3,5], target = 8
Output
[[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; }
tempResult.Add(candidates[i]);
if (candidates[i] == gap)
{
result.Add(new List < int>(tempResult));
}
else
{
DeepFirstSearch(candidates, gap - candidates[i], i, tempResult, result);
}
tempResult.RemoveAt(tempResult.Count - 1);
}
}
}
}
Input
candidates = [2], target = 1
Output
[]