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 (https://alkeshghorpade.me/post/leetcode-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]].
Top comments (1)
doing great bro..