77. Combinations

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/combinations
• topics: Backtracking

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.

Simple recursion not very efficient

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
 
        def combine(*prev, index = 0, depth = 0):
            nonlocal ans
            if not depth:
                ans.append(prev)
                return
            for i in range(index + 1, n + 1):
                combine(*prev, i, index = i, depth = depth - 1)
 
        combine(index = 0, depth = k)
        return ans

Backtracking better

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(curr, first_num):
            if len(curr) == k:
                ans.append(curr[:])
                return
 
            need = k - len(curr)
            remain = n - first_num + 1
            available = remain - need
 
            for num in range(first_num, first_num + available + 1):
                curr.append(num)
                backtrack(curr, num + 1)
                curr.pop()
 
        ans = []
        backtrack([], 1)
        return ans

Itertools most efficient

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(combinations(range(1, n+1), k))