Problem Statement:
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers
1through9are 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.
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 <= 91 <= n <= 60
Approach:
- We need to find all combinations of k numbers (from 1 to 9) that sum up to n.
- Use backtracking:
- Keep track of the current path (
path) and remaining sum (remainingSum). - Stop if the path size reaches
k. IfremainingSum == 0, record the path. - Iterate numbers from start to 9 to avoid reuse and ensure ascending order.
- Add the number, recurse with updated sum and next start, then remove (backtrack).
- Keep track of the current path (
Dry Run
Input: k = 3, n = 7
Step 0: Start Function combinationKSum(3, 7)
Initialize:
result = []
path = []
Call backtrack(7, [], 1)
Loop i = 1
path.push(1) → path = [1]
Call backtrack(6, [1], 2)
Loop i = 2
path.push(2) → path = [1, 2]
Call backtrack(4, [1, 2], 3)
Loop i = 3
path.push(3) → path = [1, 2, 3]
Call backtrack(1, [1, 2, 3], 4)
path.length == 3 but remainingSum = 1 ≠ 0 → return
path.pop() → path = [1, 2]
Loop i = 4
path.push(4) → path = [1, 2, 4]
Call backtrack(0, [1, 2, 4], 5)
path.length == 3 and remainingSum == 0 → result.push([1, 2, 4])
path.pop() → path = [1, 2]
Loop ends
path.pop() → path = [1]
Loop i = 3
path.push(3) → path = [1, 3]
Call backtrack(3, [1, 3], 4)
Loop i = 4
path.push(4) → path = [1, 3, 4]
Call backtrack(-1, [1, 3, 4], 5)
remainingSum < 0 → return
path.pop() → path = [1, 3]
Loop ends
path.pop() → path = [1]
Loop i = 4
path.push(4) → path = [1, 4]
Call backtrack(2, [1, 4], 5)
Loop i = 5
path.push(5) → path = [1, 4, 5]
Call backtrack(-3, [1, 4, 5], 6)
remainingSum < 0 → return
path.pop() → path = [1, 4]
Loop ends
path.pop() → path = [1]
Loop i = 2
path.push(2) → path = [2]
Call backtrack(5, [2], 3)
Loop i = 3
path.push(3) → path = [2, 3]
Call backtrack(2, [2, 3], 4)
Loop i = 4
path.push(4) → path = [2, 3, 4]
Call backtrack(-2, [2, 3, 4], 5)
remainingSum < 0 → return
path.pop() → path = [2, 3]
Loop ends
path.pop() → path = [2]
Loop i = 4
path.push(4) → path = [2, 4]
Call backtrack(1, [2, 4], 5)
Loop i = 5
path.push(5) → path = [2, 4, 5]
Call backtrack(-4, [2, 4, 5], 6)
remainingSum < 0 → return
path.pop() → path = [2, 4]
Loop ends
path.pop() → path = [2]
Loop ends
path.pop() → path = []
Loop i = 3, 4, 5 ... → no valid 3-number combos left within sum = 7
Step 3: End
Return result = [[1, 2, 4]]
Output:
[[1, 2, 4]]
Explanation: The only combination of k = 3 numbers from 1..9 that sums to 7 is [1, 2, 4]. Each number is used at most once because recursion advances with i+1.
var combinationSum3 = function(k, n) {
let result = [];
let backtrack = (remainingSum, path, start) => {
if(path.length == k){
if(remainingSum === 0){
result.push([...path]);
}
return;
}
for(let i=start; i<=9; i++){
path.push(i);
backtrack(remainingSum - i, path, i+1);
path.pop();
}
}
backtrack(n, [], 1)
return result;
};
def combinationSum3(k, n):
result = []
def backtrack(remainingSum, path, start):
if len(path) == k:
if remainingSum == 0:
result.append(path[:])
return
for i in range(start, 10):
path.append(i)
backtrack(remainingSum - i, path, i+1)
path.pop()
backtrack(n, [], 1)
return result
# Example usage
print(combinationSum3(3, 7))
import java.util.*;
class Solution {
public List> combinationSum3(int k, int n) {
List> result = new ArrayList<>();
backtrack(n, k, new ArrayList<>(), 1, result);
return result;
}
void backtrack(int remainingSum, int k, List path, int start, List> result) {
if (path.size() == k) {
if (remainingSum == 0) {
result.add(new ArrayList<>(path));
}
return;
}
for (int i = start; i <= 9; i++) {
path.add(i);
backtrack(remainingSum - i, k, path, i + 1, result);
path.remove(path.size() - 1);
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.combinationSum3(3, 7));
}
}
class Solution {
public:
vector> combinationSum3(int k, int n) {
vector> result;
vector path;
backtrack(n, k, path, 1, result);
return result;
}
void backtrack(int remainingSum, int k, vector& path, int start, vector>& result) {
if(path.size() == k){
if(remainingSum == 0){
result.push_back(path);
}
return;
}
for(int i=start; i<=9; i++){
path.push_back(i);
backtrack(remainingSum - i, k, path, i+1, result);
path.pop_back();
}
}
};
int main(){
Solution s;
int k=3, n=7;
vector> ans = s.combinationSum3(k,n);
for(auto &vec : ans){
for(int x : vec) cout << x << " ";
cout << "\n";
}
}
int result[100][10];
int resultSize = 0;
int path[10];
void backtrack(int remainingSum, int k, int pathSize, int start) {
if (pathSize == k) {
if (remainingSum == 0) {
for (int i = 0; i < pathSize; i++) {
result[resultSize][i] = path[i];
}
resultSize++;
}
return;
}
for (int i = start; i <= 9; i++) {
path[pathSize] = i;
backtrack(remainingSum - i, k, pathSize + 1, i + 1);
}
}
int main() {
int k = 3, n = 7;
backtrack(n, k, 0, 1);
for (int i = 0; i < resultSize; i++) {
for (int j = 0; j < k; j++) {
printf(" %d ", result[i][j]);
}
printf("\n");
}
return 0;
}
class Solution
{
public IList> CombinationSum3(int k, int n)
{
var result = new List>();
Backtrack(n, k, new List(), 1, result);
return result;
}
void Backtrack(int remainingSum, int k, List path, int start, IList> result)
{
if (path.Count == k)
{
if (remainingSum == 0)
{
result.Add(new List(path));
}
return;
}
for (int i = start; i <= 9; i++)
{
path.Add(i);
Backtrack(remainingSum - i, k, path, i + 1, result);
path.RemoveAt(path.Count - 1);
}
}
static void Main()
{
Solution s = new Solution();
var ans = s.CombinationSum3(3, 7);
foreach (var comb in ans)
{
Console.WriteLine(string.Join(" ", comb));
}
}
}
