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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<IList<int>> CombinationSum3(int k, int n) {
6 IList<IList<int>> results = new List<IList<int>>();
7 Backtrack(k, n, 1, new List<int>(), results);
8 return results;
9 }
10
11 private void Backtrack(int k, int n, int start, List<int> path, IList<IList<int>> results) {
12 if (k == 0 && n == 0) {
13 results.Add(new List<int>(path));
14 return;
15 }
16 for (int i = start; i <= 9; i++) {
17 if (i > n) break;
18 path.Add(i);
19 Backtrack(k - 1, n - i, i + 1, path, results);
20 path.RemoveAt(path.Count - 1);
21 }
22 }
23
24 public static void Main() {
25 Solution sol = new Solution();
26 IList<IList<int>> result = sol.CombinationSum3(3, 7);
27 foreach (var list in result) {
28 Console.WriteLine(string.Join(", ", list));
29 }
30 }
31}The C# code operates similarly to previous examples, using a recursive approach. The function Backtrack adjusts the combination being tested, while results are accumulated in the list results when combinations are valid.
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
In JavaScript, bitmasking navigates through all subsets deriving from numbers 1 through 9. It uses bitwise operations to create and track subsets whose lengths are k and whose totals align with n, saving matching results respectively.