Sponsored
Sponsored
This method uses a backtracking technique, where we recursively build each combination by adding numbers incrementally and backtrack whenever we've constructed combinations of size k or cannot extend further.
Time Complexity: O(C(n, k) * k), where C(n, k) is the binomial coefficient. Each combination is built in O(k) time.
Space Complexity: O(k) due to the recursion stack storing the current combination.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5 public List<List<Integer>> combine(int n, int k) {
6 List<List<Integer>> result = new ArrayList<>();
7 backtrack(n, k, 1, new ArrayList<>(), result);
8 return result;
9 }
10
11 private void backtrack(int n, int k, int start, List<Integer> current, List<List<Integer>> result) {
12 if (current.size() == k) {
13 result.add(new ArrayList<>(current));
14 return;
15 }
16 for (int i = start; i <= n; ++i) {
17 current.add(i);
18 backtrack(n, k, i + 1, current, result);
19 current.remove(current.size() - 1);
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution solution = new Solution();
25 List<List<Integer>> combinations = solution.combine(4, 2);
26 for (List<Integer> combo : combinations) {
27 System.out.println(combo);
28 }
29 }
30}The Java implementation relies on the ArrayList class for dynamic array handling, with the backtrack method recursively forming combinations, similar to how it's done in C++.
Bit masking provides a novel way to generate combinations by representing choice decisions (e.g., pick or skip) in binary. A bit mask is applied to the set of numbers [1...n], and for each bit position, if the bit is set, that number is included in the combination.
Time Complexity: O(2n * n), as we iterate over all possible subsets of [1...n] and check the bit count.
Space Complexity: O(C(n, k) * k) for storing all combinations.
1
This code generates all possible bit masks for integers from 0 to 2n-1, checking for those that have exactly k bits set. The function __builtin_popcount is used to count the number of set bits in the mask, indicating how many items in the set are chosen for a combination.