algoadvance

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Examples

Example 1:

Input: n = 4, k = 2
Output: 
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: 
[
  [1]
]

Constraints

1. 1 <= n <= 20
2. 1 <= k <= n

Clarifying Questions

1. Can n and k ever be negative or zero?
   • No, according to the constraints, n and k will be positive integers within the given range.
2. Do the elements within each combination need to be in any particular order?
   • Yes, the combination should be in ascending order, naturally implied by the problem (numeric nature).

Strategy

1. We need to generate all possible combinations. A combination is a selection of items without considering the order.
2. We can use backtracking to generate all the possible combinations.
   • Start with an empty list for the current combination.
   • Iterate from the current start point to n.
   • For each number, add it to the current combination and recurse with the next number.
   • If the combination size is k, add it to the result list.
   • Backtrack by removing the last added number.
3. Utilize depth-first search (DFS) with backtracking to explore all potential combinations.

Code

Here’s the implementation using the above strategy:

def combine(n: int, k: int):
    def backtrack(start, comb):
        # If the combination is complete
        if len(comb) == k:
            result.append(list(comb))  # Add a copy of comb
            return
        
        for i in range(start, n + 1):
            # Add i into the current combination
            comb.append(i)
            # Use next integers to complete the combination
            backtrack(i + 1, comb)
            # Backtrack by removing the last added number
            comb.pop()
    
    result = []
    backtrack(1, [])
    return result

# Example usage:
print(combine(4, 2))  # Outputs the combinations

Time Complexity

The time complexity of generating combinations can be understood as follows:

• There are C(n, k) combinations, which is the number of ways to choose k elements from n elements without regarding the order.
• Therefore, the time complexity is O(C(n, k) * k) because for each combination, it takes linear time, k, to process it (adding to results and so forth).

For space complexity, we store all the combinations and also use recursive calls:

• Space complexity is O(C(n, k) * k) for storing the results.

This makes the approach efficient and feasible given the problem’s constraints of n up to 20.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?