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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Combinations

Difficulty: Medium

Problem Description

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

Key Insights

  • The problem requires generating combinations, which can be approached using backtracking.
  • Each combination can be constructed by choosing an integer and recursively building on it.
  • The order of numbers in combinations does not matter, meaning [1, 2] is the same as [2, 1].
  • The constraints (1 <= n <= 20) allow for a backtracking solution without performance concerns.

Space and Time Complexity

Time Complexity: O(C(n, k) * k) where C(n, k) is the binomial coefficient representing the number of combinations, and k is the length of each combination. Space Complexity: O(k) for the recursion stack and storage of combinations.

Solution

The solution utilizes a backtracking approach to explore all possible combinations of k numbers from the set {1, 2, ..., n}. A helper function is used to build combinations incrementally, maintaining the current combination and the starting point for the next number to ensure that combinations are unique and ordered.

Code Solutions

def combine(n, k):
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    result = []
    backtrack(1, [])
    return result
← Back to All Questions