 # LeetCode - Combination Sum

### Problem statement

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 frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Problem statement taken from: https://leetcode.com/problems/combination-sum/.

Example 1:

``````Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], ]
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 = , target = 1
Output: []``````

Constraints:

``````- 1 <= candidates.length <= 30
- 1 <= candidates[i] <= 200
- All elements of candidates are distinct.
- 1 <= target <= 500``````

### Explanation

#### Brute force approach

The brute force approach is to generate all combinations and verify the elements in the array sum up to target or not.

But the time complexity of the above program will be O(N^2).

#### Backtracking

These kinds of problems can be solved using backtracking. We write a recursive function where we keep appending the array elements to a temporary array (called current) and keep tracking the sum of the elements in this temporary array. Inside the recursive function, we keep two base cases.

1. The first base case is to check if the sum of the elements in the temporary array is equal to the target. If yes we return and append the temporary array to the final result.

2. The second base case is to check if the sum exceeds the target element we just return.

Let's check the algorithm to clearly understand the above approach.

``````- initialize the result as a 2D array
initialize current as an array

// n = index, at start it will be 0.
// sumTillNow = sum of the current elements in the array, at the start it will be 0
// current = current list of elements in the array, at the start it will be an empty array []
- call combinationSumUtil(result, candidates, n, target, sumTillNow, current)

- return result

// combinationSumUtil function
- if sumTillNow == target
// append current to result
- result.push_back(current)

- if sumTillNow > target
- return

- loop for i = n; i <= candidates.size() - 1; i++
// append candidates array ith element to the current array
- current.push_back(candidates[i])

- sumTillNow += candidates[i]

// call the function recursively
- combinationSumUtil(result, candidates, i, target, sumTillNow, current)

- sumTillNow -= current[current.size() - 1]

// remove the last element from the array
- current.pop_back()``````

Let's check out our solutions in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
void combinationSumUtil(vector<vector<int>>& result, vector<int>& candidates, int n, int target, int sumTillNow, vector<int>& current) {
if(sumTillNow == target) {
result.push_back(current);
}

if(sumTillNow > target) {
return;
}

for(int i = n; i <= candidates.size() - 1; i++) {
current.push_back(candidates[i]);
sumTillNow += candidates[i];

combinationSumUtil(result, candidates, i, target, sumTillNow, current);

sumTillNow -= current[current.size() - 1];
current.pop_back();
}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> current;

combinationSumUtil(result, candidates, 0, target, 0, current);
return result;
}
};``````

#### Golang solution

``````func combinationSumUtil(result *[][]int, candidates []int, n, target, sumTillNow int, current []int) {
if sumTillNow == target {
*result = append(*result, append([]int{}, current...))
return
}

if sumTillNow > target {
return
}

for i := n; i <= len(candidates) - 1; i++ {
current = append(current, candidates[i])
sumTillNow = sumTillNow + candidates[i]

combinationSumUtil(result, candidates, i, target, sumTillNow, current)

sumTillNow = sumTillNow - current[len(current) - 1]
current = current[:len(current) - 1]
}
}

func combinationSum(candidates []int, target int) [][]int {
result := make([][]int, 0)

combinationSumUtil(&result, candidates, 0, target, 0, []int{})

return result
}``````

#### Javascript solution

``````var combinationSum = function(candidates, target) {
let result = [];

const combinationSumUtil = (candidates, n, target, sumTillNow, current) => {
if(sumTillNow === target) {
result.push([...current]);
}

if(sumTillNow > target) {
return;
}

for(let i = n; i <= candidates.length - 1; i++){
current.push(candidates[i]);
sumTillNow += candidates[i];

combinationSumUtil(candidates, i, target, sumTillNow, current);

sumTillNow -= current[current.length - 1];
current.pop();
}
}

combinationSumUtil(candidates, 0, target, 0, []);

return result;
};``````

Let's dry run our algorithm.

``````Input: candidates = [2, 3, 6, 7]
target = 7

// combinationSum function
Step 1: vector<vector<int>> result
vector<int> current

Step 2: combinationSumUtil(result, candidates, 0, target, 0, current)

// combinationSumUtil function
Step 3: if sumTillNow == target
0 == 7
false

if sumTillNow > target
0 > 7
false

loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(2)
current = 

sumTillNow += candidates[i]
= sumTillNow + candidates
= 0 + 2
= 2

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 2, )

Step 4: if sumTillNow == target
2 == 7
false

if sumTillNow > target
2 > 7
false

loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(2)
current = [2, 2]

sumTillNow += candidates[i]
= sumTillNow + candidates
= 2 + 2
= 4

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 4, [2, 2])

Step 5: if sumTillNow == target
4 == 7
false

if sumTillNow > target
4 > 7
false

loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(2)
current = [2, 2, 2]

sumTillNow += candidates[i]
= sumTillNow + candidates
= 4 + 2
= 6

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 6, [2, 2, 2])

Step 6: if sumTillNow == target
6 == 7
false

if sumTillNow > target
6 > 7
false

loop for int i = n; i <= candidates.size() - 1
i = 0
i <= 4 - 1
0 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(2)
current = [2, 2, 2, 2]

sumTillNow += candidates[i]
= sumTillNow + candidates
= 6 + 2
= 8

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 8, [2, 2, 2, 2])

Step 7: if sumTillNow == target
8 == 7
false

if sumTillNow > target
8 > 7
true
return

we backtrack to step 6 and continue

Step 8: combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 8, [2, 2, 2, 2])
sumTillNow = sumTillNow - current[len(current) - 1]
= 8 - current[4 - 1]
= 8 - current
= 8 - 2
= 6

current.pop_back()
current = [2, 2, 2]

i++
i = 1

i = 1
i <= 4 - 1
1 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(3)
current = [2, 2, 2, 3]

sumTillNow += candidates[i]
= 6 + candidates
= 6 + 3
= 9

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])

Step 9: if sumTillNow == target
9 == 7
false

if sumTillNow > target
9 > 7
true
return

we backtrack to step 8 and continue

Step 10:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])
sumTillNow = sumTillNow - current[len(current) - 1]
= 9 - current[4 - 1]
= 9 - current
= 9 - 3
= 6

current.pop_back()
current = [2, 2, 2]

i++
i = 2

i = 2
i <= 4 - 1
2 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(6)
current = [2, 2, 2, 6]

sumTillNow += candidates[i]
= 6 + candidates
= 6 + 6
= 12

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 12, [2, 2, 2, 6])

Step 11: if sumTillNow == target
12 == 7
false

if sumTillNow > target
12 > 7
true
return

we backtrack to step 10 and continue

Step 12:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])
sumTillNow = sumTillNow - current[len(current) - 1]
= 12 - current[4 - 1]
= 12 - current
= 12 - 6
= 6

current.pop_back()
current = [2, 2, 2]

i++
i = 3

i = 3
i <= 4 - 1
3 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(7)
current = [2, 2, 2, 7]

sumTillNow += candidates[i]
= 6 + candidates
= 6 + 7
= 13

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 13, [2, 2, 2, 7])

Step 13: if sumTillNow == target
13 == 7
false

if sumTillNow > target
13 > 7
true
return

we backtrack to step 12 and continue

Step 14:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 9, [2, 2, 2, 3])
sumTillNow = sumTillNow - current[len(current) - 1]
= 13 - current[4 - 1]
= 13 - current
= 13 - 7
= 6

current.pop_back()
current = [2, 2, 2]

i++
i = 4

i = 3
i <= 4 - 1
4 <= 3
false

Step 15:combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 6, [2, 2, 2])
sumTillNow = sumTillNow - current[len(current) - 1]
= 6 - current[3 - 1]
= 6 - current
= 6 - 2
= 4

current.pop_back()
current = [2, 2]

i++
i = 1

i = 1
i <= 4 - 1
1 <= 3
true

current.push_back(candidates[i])
current.push_back(candidates)
current.push_back(3)
current = [2, 2, 3]

sumTillNow += candidates[i]
= 4 + candidates
= 4 + 3
= 7

combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 7, [2, 2, 3])

Step 16:if sumTillNow == target
7 == 7
true

result.push_back(current)
result.push_back([2, 2, 3])

result = [[2, 2, 3]]

Similarly, we iterate over all other elements and get the result as
[[2, 2, 3], ]``````