We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Combinations

Number: 77

Difficulty: Medium

Paid? No

Companies: Google, Meta, Microsoft, Amazon, Bloomberg, TikTok, Adobe, Apple

Problem Description

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. The answer can be returned in any order.

Key Insights

  • The problem requires generating all unique combinations (order does not matter) from 1 to n.
  • Backtracking (depth-first search) is ideal for exploring all possible combinations.
  • We build combinations incrementally and backtrack when the current combination reaches a dead end or a complete combination of k numbers is formed.
  • Pruning the recursion early by limiting the candidate range helps improve efficiency.

Space and Time Complexity

Time Complexity: O(k * C(n, k))
Space Complexity: O(k) for the recursion stack (not including space for the output)

Solution

We use a backtracking approach with depth-first search to generate all possible combinations. Start with an empty combination and recursively add numbers from a candidate range ensuring each new element is greater than the last added, which maintains the increasing order and avoids duplicates. When the length of the current combination equals k, add it to the result list. After exploring each path, backtrack by removing the last element and try the next number. The candidate range can be pruned since if the remaining numbers are insufficient to reach k, no further recursive calls are made.

Code Solutions

# Define the function to get combinations
def combine(n, k):
    # This list will store all the valid combinations
    result = []
    
    # Helper function for backtracking
    def backtrack(start, current):
        # If current combination is of the required length, add a copy to result
        if len(current) == k:
            result.append(current.copy())
            return
        
        # Iterate from the current start to n
        # Prune the loop: Stop if remaining numbers are less than needed
        for num in range(start, n + 1):
            # Add the current number to the combination
            current.append(num)
            # Move on to the next number; increment start to ensure increasing order
            backtrack(num + 1, current)
            # Remove the last added number to backtrack
            current.pop()
    
    # Initialize backtracking with starting number 1 and an empty combination
    backtrack(1, [])
    return result

# Example usage
print(combine(4, 2))
← Back to All Questions