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.
1def combinationSum3(k, n):
2 def backtrack(k, n, start, path, results):
3 if k == 0 and n == 0:
4 results.append(list(path))
5 return
6 for i in range(start, 10):
7 if n < i:
8 break
9 path.append(i)
10 backtrack(k - 1, n - i, i + 1, path, results)
11 path.pop()
12
13 results = []
14 backtrack(k, n, 1, [], results)
15 return results
16
17# Example Usage:
18# print(combinationSum3(3, 7))This Python example similarly utilizes a recursive backtracking approach. The helper function backtrack attempts all combinations from start to 9 using recursion. Solutions are added to results when valid combinations are identified.
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.