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.
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.