Dare2Solve
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.
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.
Initialization:
Backtracking Function:
k
numbers and the sum equals n
, add it to the result list.n
or if the combination is not valid, terminate that branch of recursion.Base Case:
k
and the sum equals n
, add the combination to the results.Recursion:
Backtrack:
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.
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
.
class Solution {
public:
std::vector<std::vector<int>> combinationSum3(int k, int n) {
std::vector<std::vector<int>> result;
std::vector<int> combination;
std::vector<int> 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<int>& nums, int k, int n, int start,
std::vector<int>& combination, std::vector<std::vector<int>>& 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
}
}
};
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
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> 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<Integer> combination, List<List<Integer>> 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
}
}
}
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;
};