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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class CombinationSum3 {
5 private void backtrack(int k, int n, int start, List<Integer> path, List<List<Integer>> results) {
6 if (k == 0 && n == 0) {
7 results.add(new ArrayList<>(path));
8 return;
9 }
10 for (int i = start; i <= 9; i++) {
11 if (i > n) break;
12 path.add(i);
13 backtrack(k - 1, n - i, i + 1, path, results);
14 path.remove(path.size() - 1);
15 }
16 }
17
18 public List<List<Integer>> combinationSum3(int k, int n) {
19 List<List<Integer>> results = new ArrayList<>();
20 backtrack(k, n, 1, new ArrayList<>(), results);
21 return results;
22 }
23
24 public static void main(String[] args) {
25 CombinationSum3 solver = new CombinationSum3();
26 List<List<Integer>> result = solver.combinationSum3(3, 7);
27 for (List<Integer> list : result) {
28 System.out.println(list);
29 }
30 }
31}This Java solution utilizes backtracking with helper function backtrack. The list path holds numbers in current sequence. Recursive calls progressively attempt further numbers, while restored elements in path enable backtracking.
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
This Java code features non-recursive bitmask exploration, iterating over all subsets as integers 1 through 9 determine sequence membership. Using bitwise operations, subsets producing length k and sum n are collected.