LeetCode - Combination Sum III
Problem statement
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers 1 through 9 are used.
- Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Problem statement taken from: https://leetcode.com/problems/combination-sum-iii.
Example 1:
Input: k = 3, n = 7
Output: [[1, 2, 4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:
Input: k = 3, n = 9
Output: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:
Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1, 9], the smallest sum we can get
is 1 + 2 + 3 + 4 = 10 and since 10 > 1, there are no valid combination.
Constraints:
- 2 <= k <= 9
- 1 <= n <= 60
Explanation
Backtracking
The problem can be solved using the similar approach we used in our previous two blogs Combination Sum II and Combination Sum. In this problem, we are not given any input array instead, we need to use numbers from 1 to 9.
Let's check the algorithm to see how the solution works.
- initialize the result as a 2D array
initialize current as an array
// current = current list of elements in the array at the start it will be an empty array []
// currentIndex = index, at start it will be 1.
// sumTillNow = sum of the current elements in the array at the start it will be 0
// numsAddedTillNow = count of numbers present in current array.
- call combinationSum2Util(result, current, currentIndex, sumTillNow, numsAddedTillNow, k, n)
- return result
// combinationSum3Util function
- if numsAddedTillNow == k && sumTillNow == n
// append current to result
- result.push_back(current)
- if numsAddedTillNow > k || sumTillNow == n
- return
- loop for i = currentIndex; i <= 9; i++
- sumTillNow = sumTillNow + i
- current.push_back(i)
- numsAddedTillNow = numsAddedTillNow + 1
// call the function recursively
- combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
- sumTillNow = sumTillNow - i
- current.pop_back()
- numsAddedTillNow = numsAddedTillNow - 1
Let's check our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
void combinationSum3Util(vector<vector<int>> &result, vector<int>& current, int currentIndex, int sumTillNow, int numsAddedTillNow, int k, int n) {
if(numsAddedTillNow == k && sumTillNow == n) {
result.push_back(current);
return;
}
if(numsAddedTillNow > k || sumTillNow > n) {
return;
}
for(int i = currentIndex; i <= 9; i++) {
sumTillNow += i;
current.push_back(i);
numsAddedTillNow++;
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n);
sumTillNow -= i;
current.pop_back();
numsAddedTillNow--;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> current;
combinationSum3Util(result, current, 1, 0, 0, k, n);
return result;
}
};Golang solution
func combinationSum3Util(result *[][]int, current []int, currentIndex, sumTillNow, numsAddedTillNow, k, n int) {
if numsAddedTillNow == k && sumTillNow == n {
*result = append(*result, append([]int{}, current...))
return
}
if numsAddedTillNow > k || sumTillNow > n {
return
}
for i := currentIndex; i <= 9; i++ {
sumTillNow += i
current = append(current, i)
numsAddedTillNow++
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
sumTillNow -= i
current = current[:len(current) - 1]
numsAddedTillNow--
}
}
func combinationSum3(k int, n int) [][]int {
result := make([][]int, 0)
combinationSum3Util(&result, []int{}, 1, 0, 0, k, n)
return result
}Javascript solution
var combinationSum3 = function(k, n) {
let result = [];
const combinationSum3Util = (current, currentIndex, sumTillNow, numsAddedTillNow, k, n) => {
if(numsAddedTillNow == k && sumTillNow == n) {
result.push([...current]);
return;
}
if(numsAddedTillNow > k || sumTillNow > n) {
return;
}
for(let i = currentIndex; i <= 9; i++) {
sumTillNow += i;
current.push(i);
numsAddedTillNow++;
combinationSum3Util(current, i + 1, sumTillNow, numsAddedTillNow, k, n);
sumTillNow -= i;
current.pop();
numsAddedTillNow--;
}
}
combinationSum3Util([], 1, 0, 0, k, n);
return result;
};Let's dry run our algorithm for a few iterations and recursion.
Input: k = 3, n = 7
// combinationSum function
Step 1: vector<vector<int>> result
vector<int> current
Step 2: combinationSum3Util(result, current, 1, 0, 0, k, n)
// combinationSum2Util function
Step 3: if numsAddedTillNow == k && sumTillNow == n
0 == 3 && 0 == 7
false
if numsAddedTillNow > k || sumTillNow > n
0 > 3 || 0 > 7
false
loop for i = currentIndex; i <= 9
i = 1
i <= 9
true
sumTillNow = sumTillNow + i
= 0 + 1
= 1
current.push_back(i)
current = [1]
numsAddedTillNow = numsAddedTillNow + 1
= 0 + 1
= 1
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
combinationSum3Util([[]], [1], 1 + 1, 1, 1, 3, 7)
combinationSum3Util([[]], [1], 2, 1, 1, 3, 7)
Step 4: if numsAddedTillNow == k && sumTillNow == n
1 == 3 && 1 == 7
false
if numsAddedTillNow > k || sumTillNow > n
1 > 3 || 1 > 7
false
loop for i = currentIndex; i <= 9
i = 2
i <= 9
true
sumTillNow = sumTillNow + i
= 1 + 2
= 3
current.push_back(i)
current.push_back(2)
current = [1, 2]
numsAddedTillNow = numsAddedTillNow + 1
= 1 + 1
= 2
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
combinationSum3Util([[]], [1, 2], 1 + 1, 3, 2, 3, 7)
combinationSum3Util([[]], [1, 2], 2, 3, 2, 3, 7)
Step 5: if numsAddedTillNow == k && sumTillNow == n
2 == 3 && 3 == 7
false
if numsAddedTillNow > k || sumTillNow > n
2 > 3 || 3 > 7
false
loop for i = currentIndex; i <= 9
i = 3
i <= 9
true
sumTillNow = sumTillNow + i
= 3 + 3
= 6
current.push_back(i)
current.push_back(3)
current = [1, 2, 3]
numsAddedTillNow = numsAddedTillNow + 1
= 2 + 1
= 3
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
combinationSum3Util([[]], [1, 2, 3], 2 + 1, 6, 3, 3, 7)
combinationSum3Util([[]], [1, 2, 3], 3, 6, 3, 3, 7)
Step 6: if numsAddedTillNow == k && sumTillNow == n
3 == 3 && 3 == 7
false
if numsAddedTillNow > k || sumTillNow > n
3 > 3 || 6 > 7
false
loop for i = currentIndex; i <= 9
i = 4
i <= 9
true
sumTillNow = sumTillNow + i
= 6 + 4
= 10
current.push_back(i)
current.push_back(4)
current = [1, 2, 3, 4]
numsAddedTillNow = numsAddedTillNow + 1
= 3 + 1
= 4
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
combinationSum3Util([[]], [1, 2, 3, 4], 3 + 1, 10, 4, 3, 7)
combinationSum3Util([[]], [1, 2, 3, 4], 4, 10, 4, 3, 7)
Step 7: if numsAddedTillNow == k && sumTillNow == n
4 == 3 && 10 == 7
false
if numsAddedTillNow > k || sumTillNow > n
4 > 3 || 10 > 7
true
return
we backtrack to step 6
Step 8: combinationSum3Util([[]], [1, 2, 3, 4], 4, 10, 4, 3, 7)
sumTillNow = sumTillNow - i
= 10 - 4
= 6
current.pop_back()
current = [1, 2, 3]
numsAddedTillNow = numsAddedTillNow - 1
= 4 - 1
= 3
i++
i = 5
loop for i = currentIndex; i <= 9
i = 5
i <= 9
true
sumTillNow = sumTillNow + i
= 6 + 5
= 11
current.push_back(i)
current.push_back(5)
current = [1, 2, 3, 5]
numsAddedTillNow = numsAddedTillNow + 1
= 3 + 1
= 4
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
combinationSum3Util([[]], [1, 2, 3, 5], 3 + 1, 11, 4, 3, 7)
combinationSum3Util([[]], [1, 2, 3, 5], 4, 11, 4, 3, 7)
Step 9: if numsAddedTillNow == k && sumTillNow == n
4 == 3 && 11 == 7
false
if numsAddedTillNow > k || sumTillNow > n
4 > 3 || 11 > 7
true
return
we backtrack to step 8 and this gets repeated till i or currentIndex is 9.
From all these steps, we backtrack to step 6.
Step 10...11...17:
Step 18: combinationSum3Util([[]], [1, 2, 3], 3, 6, 3, 3, 7)
sumTillNow = sumTillNow - i
= 6 - 3
= 3
current.pop_back()
current = [1, 2]
numsAddedTillNow = numsAddedTillNow - 1
= 3 - 1
= 2
i++
i = 4
loop for i = currentIndex; i <= 9
i = 4
i <= 9
true
sumTillNow = sumTillNow + i
= 3 + 4
= 7
current.push_back(i)
current.push_back(4)
current = [1, 2, 4]
numsAddedTillNow = numsAddedTillNow + 1
= 2 + 1
= 3
combinationSum3Util(result, current, i + 1, sumTillNow, numsAddedTillNow, k, n)
combinationSum3Util([[]], [1, 2, 4], 2 + 1, 7, 3, 3, 7)
combinationSum3Util([[]], [1, 2, 4], 3, 7, 3, 3, 7)
Step 19: if numsAddedTillNow == k && sumTillNow == n
3 == 3 && 7 == 7
true
result.push_back(current)
result = [[1, 2, 4]]
return
The backtracking continues till we reach currentIndex = 10.
We return the answer as [[1, 2, 4]].