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], [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
- 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.
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.
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[0])
current.push_back(2)
current = [2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 0 + 2
= 2
combinationSumUtil(result, candidates, i, target, sumTillNow, current)
combinationSumUtil([][], [2, 3, 6, 7], 0, 7, 2, [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[0])
current.push_back(2)
current = [2, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 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[0])
current.push_back(2)
current = [2, 2, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 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[0])
current.push_back(2)
current = [2, 2, 2, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 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[3]
= 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[1])
current.push_back(3)
current = [2, 2, 2, 3]
sumTillNow += candidates[i]
= 6 + candidates[1]
= 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[3]
= 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[2])
current.push_back(6)
current = [2, 2, 2, 6]
sumTillNow += candidates[i]
= 6 + candidates[2]
= 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[3]
= 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[3])
current.push_back(7)
current = [2, 2, 2, 7]
sumTillNow += candidates[i]
= 6 + candidates[3]
= 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[3]
= 13 - 7
= 6
current.pop_back()
current = [2, 2, 2]
i++
i = 4
i = 3
i <= 4 - 1
4 <= 3
false
We return to Step 5 directly
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[2]
= 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[1])
current.push_back(3)
current = [2, 2, 3]
sumTillNow += candidates[i]
= 4 + candidates[1]
= 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], [7]]