Sponsored
Sponsored
This approach uses backtracking to explore all possible combinations. Start with an empty combination, then add numbers incrementally and explore subsequent possibilities. If the sum of combination exceeds n or if it reaches the required length k, backtracking occurs to explore other potential combinations.
Time Complexity: O(2^n) because each number has a choice of being included or not.
Space Complexity: O(k) for the recursion stack.
1var combinationSum3 = function(k, n) {
2 const results = [];
3 function backtrack(k, n, start, path) {
4 if (k === 0 && n === 0) {
5 results.push([...path]);
6 return;
7 }
8 for (let i = start; i <= 9; i++) {
9 if (n < i) break;
10 path.push(i);
11 backtrack(k - 1, n - i, i + 1, path);
12 path.pop();
13 }
14 }
15 backtrack(k, n, 1, []);
16 return results;
17};
18
19// Example Usage:
20// console.log(combinationSum3(3, 7));This JavaScript example uses backtracking within the backtrack function. It iteratively tests valid combinations, tracking progress with the array path. Valid combinations are stored in results.
This approach leverages bitmasking to generate all subsets of numbers {1,2,...,9} and filters conceivable combinations by size and sum criteria. It's potentially less intuitive, yet eliminates recursion.
Time Complexity: O(2^n), iterating through bitmask combinations for validity checks.
Space Complexity: O(k) due to maintained size of data array.
1#include <vector>
using namespace std;
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
for (int mask = 0; mask < (1 << 9); ++mask) {
vector<int> comb;
int sum = 0;
for (int i = 0; i < 9; ++i) {
if (mask & (1 << i)) {
sum += (i + 1);
comb.push_back(i + 1);
}
}
if (comb.size() == k && sum == n) {
result.push_back(comb);
}
}
return result;
}
// Example usage:
// int main() {
// vector<vector<int>> result = combinationSum3(3, 7);
// for (const auto& comb : result) {
// for (int num : comb) {
// cout << num << ' ';
// }
// cout << endl;
// }
// return 0;
// }This C++ solution leverages iteration and bitmasking to synthesize potential combinations. Each bitmask iterates over potential combinations from numbers 1 to 9. Valid combinations matching length and sum predicates are stored for output.