🧩 Problem Statement
Find all valid combinations of k numbers that sum up to n such that only numbers from 1 to 9 can be used and each number is used at most once.
Return a list of all possible combinations.
📘 Example
go
Input: k = 3, n = 7
Output: [[1,2,4]]
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
🧠 Approach
We use backtracking:
- Start from number 1 to 9
- Add number to current combination
- Recur with reduced target (
n - num) and one less count (k - 1)
- If both
k == 0 and n == 0, it's a valid combination
- Use pruning to improve performance
✅ Go Implementation
go
package main
import "fmt"
func combinationSum3(k int, n int) [][]int {
var result [][]int
var current []int
var backtrack func(start, k, target int)
backtrack = func(start, k, target int) {
if k == 0 && target == 0 {
combo := make([]int, len(current))
copy(combo, current)
result = append(result, combo)
return
}
if k == 0 || target < 0 {
return
}
for i := start; i <= 9; i++ {
current = append(current, i)
backtrack(i+1, k-1, target-i)
current = current[:len(current)-1]
}
}
backtrack(1, k, n)
return result
}
📦 Example Usage
go
func main() {
fmt.Println(combinationSum3(3, 7)) // Output: [[1 2 4]]
fmt.Println(combinationSum3(3, 9)) // Output: [[1 2 6] [1 3 5] [2 3 4]]
}
⏱️ Time & Space Complexity
- Time: O(C(9, k)) — All k-length combinations from 1-9
- Space: O(k) for recursion stack