
Description
The problem is to find all possible combinations of k
numbers from 1 to 9 that add up to a given number n
. Each number in the combination must be unique, and the order of numbers does not matter.
Intuition
To solve this problem, we need to explore all possible combinations of k
numbers that sum up to n
. A backtracking approach is suitable here as it allows us to explore each possible combination and backtrack when we reach an invalid state. We will use a recursive function to build combinations and only keep those that meet the criteria.
Approach
- Initialization: - Prepare a list of numbers from 1 to 9. - Initialize a list to store the results.
- Backtracking Function:
- Use a recursive function that builds combinations of numbers.
- Track the current combination and its sum.
- If the combination has exactly
k
numbers and the sum equalsn
, add it to the result list. - If the current sum exceedsn
or if the combination is not valid, terminate that branch of recursion. - Use a loop to explore all possible numbers from the current position and recursively build combinations. - Base Case:
- If the length of the current combination is
k
and the sum equalsn
, add the combination to the results. - Recursion: - For each number, add it to the current combination and recursively explore further numbers.
- Backtrack: - Remove the last number added and try the next number in sequence.
Complexity
Time Complexity:
The time complexity is O(C(9, k) * k)
, where C(9, k)
represents the number of combinations of choosing k
numbers from 9. Each combination is explored once, and the operations inside each recursive call involve adding and removing elements from the list, which takes O(k)
time.
Space Complexity:
The space complexity is O(C(9, k) * k)
due to the storage required for the result list and the space used by the recursion stack. The result list stores all valid combinations, and the maximum depth of the recursion stack is k
.
Code
C++
class Solution {
public:
std::vector> combinationSum3(int k, int n) {
std::vector> result;
std::vector combination;
std::vector nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
backtrack(nums, k, n, 0, combination, result);
return result;
}
private:
void backtrack(const std::vector& nums, int k, int n, int start,
std::vector& combination, std::vector>& result) {
if (combination.size() == k && n == 0) {
result.push_back(combination);
return;
}
for (int i = start; i < nums.size(); ++i) {
if (n < nums[i]) continue; // Skip if current number is greater than remaining sum
combination.push_back(nums[i]);
backtrack(nums, k, n - nums[i], i + 1, combination, result);
combination.pop_back(); // Remove last element to try the next candidate
}
}
};
Python
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def backtrack(start: int, combination: List[int], total: int):
if len(combination) == k and total == n:
result.append(combination[:])
return
for i in range(start, 9):
if total + (i + 1) > n:
continue
combination.append(i + 1)
backtrack(i + 1, combination, total + (i + 1))
combination.pop()
result = []
backtrack(0, [], 0)
return result
Java
public class Solution {
public List> combinationSum3(int k, int n) {
List> result = new ArrayList<>();
List combination = new ArrayList<>();
int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
backtrack(nums, k, n, 0, combination, result);
return result;
}
private void backtrack(int[] nums, int k, int n, int start,
List combination, List> result) {
if (combination.size() == k && n == 0) {
result.add(new ArrayList<>(combination));
return;
}
for (int i = start; i < nums.length; ++i) {
if (n < nums[i]) continue; // Skip if current number is greater than remaining sum
combination.add(nums[i]);
backtrack(nums, k, n - nums[i], i + 1, combination, result);
combination.remove(combination.size() - 1); // Remove last element to try the next candidate
}
}
}
JavaScript
var combinationSum3 = function (k, n) {
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let ans = [];
function helper(sum, ar, i) {
if (ar.length === k && sum === n) {
ans.push(ar);
return;
}
if (i >= n) {
if (ar.length === k && sum === n) {
ans.push(ar);
return;
}
return;
}
for (let j = i; j < arr.length; j++) {
helper(sum + arr[j], [...ar, arr[j]], j + 1);
}
}
helper(0, [], 0);
return ans;
};