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.
1#include <vector>
2using namespace std;
3
4void backtrack(int k, int n, int start, vector<int>& path, vector<vector<int>>& results) {
5 if (k == 0 && n == 0) {
6 results.push_back(path);
7 return;
8 }
9 for (int i = start; i <= 9; ++i) {
10 if (i > n) break;
11 path.push_back(i);
12 backtrack(k - 1, n - i, i + 1, path, results);
13 path.pop_back();
14 }
15}
16
17vector<vector<int>> combinationSum3(int k, int n) {
18 vector<vector<int>> results;
19 vector<int> path;
20 backtrack(k, n, 1, path, results);
21 return results;
22}
23
24// Example usage:
25// vector<vector<int>> result = combinationSum3(3, 7);
26// for (const auto& seq : result) {
27// for (int num : seq) {
28// cout << num << ' ';
29// }
30// cout << endl;
31// }The C++ code implements backtracking in a similar manner to C. The function modifies the current combination path during exploration. It explores increasingly larger numbers to maintain unique number constraints and uses a vector to store resultant combinations.
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.
1using System.Collections.Generic;
public class CombinationSum3Iterative {
public IList<IList<int>> CombinationSum3(int k, int n) {
IList<IList<int>> result = new List<IList<int>>();
for (int mask = 0; mask < (1 << 9); ++mask) {
List<int> comb = new List<int>();
int sum = 0;
for (int i = 0; i < 9; ++i) {
if ((mask & (1 << i)) != 0) {
sum += (i + 1);
comb.Add(i + 1);
}
}
if (comb.Count == k && sum == n) {
result.Add(new List<int>(comb));
}
}
return result;
}
public static void Main() {
CombinationSum3Iterative solution = new CombinationSum3Iterative();
var result = solution.CombinationSum3(3, 7);
foreach (var set in result) {
Console.WriteLine(string.Join(", ", set));
}
}
}The C# solution is aligned with bitmasking, iterating interaction courses through all potential 512 number uses outcomes from 1 to 9. Filtered results meeting specification are simply recorded in final result.