77_ Combinations

[Medium][Backtracking]

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

Example:

Input: n = 4, k = 2

Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution:

Idea:

• For integer 1, there are two possibilities: the subset does not contain 1, or it does contain 1.

  • In the first case: we return all subsets of size k from 2 ... n

  • In the second case: we return all subsets of size k-1 from 2 ... n and append 1 to each of them

• Use the same idea for each integer.

Time Complexity: $O(n\dbinom{n}{k})$ from EPI book, hard to compute because of the two parameters

Space Complexity: $O(k)$

def combine(n, k):
    """
    :type n: int
    :type k: int
    :rtype: List[List[int]]
    """
    # this helper function aims to find subset of size l 
    # from integers starting from m to n (inclusive)
    def helper(m, l):
        # m is the starting position of the left over nums
        # l is the left number of integers to use

        # corner case for only 1 integer need to be found
        # assign each candidate and append to output
        if l == 1:
            for num in range(m, n + 1):
                sol[k - 1] = num
                output.append(list(sol))
            return

        # corner case for the number of integers to be found
        # be the same as the left over integers
        if n - m + 1 == l:
            sol[k-l : k] = range(m, n + 1)
            output.append(list(sol))
            return

        # if the smallest candidate is used
        sol[k - l] = m
        helper(m + 1, l - 1)
        # if the smallest candidate is not used
        helper(m + 1, l)

    output, sol = [], [0] * k
    helper(1, k)
    return output