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.
1def combine(n, k):
2 def backtrack(start, curr):
3 if len(curr) == k:
4 result.append(curr[:])
5 return
6 for i in range(start, n+1):
7 curr.append(i)
8 backtrack(i+1, curr)
9 curr.pop()
10
11 result = []
12 backtrack(1, [])
13 return result
14
15print(combine(4, 2))The Python implementation uses a local helper function backtrack to recursively explore possible combinations, leveraging Python's list's natural dynamic size for convenient management of the current list of numbers being explored.
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.