77. Combinations

Medium LeetCode

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.

Example 1

Input: n = 4, k = 2

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

Explanation: There are 4 choose 2 = 6 total combinations. Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2

Input: n = 1, k = 1

Output: [[1]]

Explanation: There is 1 choose 1 = 1 total combination.

Constraints

• 1 <= n <= 20
• 1 <= k <= n

How to solve the problem

• Backtracking (DFS)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        def backtracking(start: int, path: List[int]):
            if len(path) == k: # Base case
                result.append(path[:]) # Copy 'path', cause it may be modified after
                return # Stop the recursion
            for i in range(start, n+1): # n+1, make sure 'n' be covered
                path.append(i)
                backtracking(i+1, path)
                path.pop() # remove the last element in list
        backtracking(1, [])
        return result

Complexity

• Time complexity: O(K*C(n, k))
• Space complexity: O(K*C(n, k))