👨‍💻 738LeetCode

Combinations

Question

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

Example

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

Solution

Backtracking.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def helper(start, curr):
            if len(curr) == k:
                ret.append(curr.copy())
                return
            for i in range(start, n):
                curr.append(nums[i])
                helper(i + 1, curr)
                curr.pop()


        nums = [i for i in range(1, n + 1)]
        ret = []
        helper(0, [])
        return ret