77.Combinations_(Medium).md

77. Combinations (Medium)

Date and Time: Jun 23, 2024, 0:14 (EST)

Link: https://leetcode.com/problems/combinations/

Question:

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.

KeyPoints:

Another typical backtracking problem. Find the two base cases, then we append each incremented element into curr, pop() to remove the current last digit and increment the current digit and start appending again.

My Solution:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        curr = []
        def dfs(i, curr):
            # Base case: when the len(curr) == k, append curr to res
            if len(curr) == k:
                res.append(curr.copy())   # Remember use .copy() to append
                return
            # Base case: if i > n, should not be append to curr
            if i > n:
                return
            curr.append(i)
            print(f"i: {i}\ncurr: {curr}")
            dfs(i+1, curr)
            curr.pop()
            dfs(i+1, curr)
        # Remember we start from 1  
        dfs(1, curr)
        return res

i: 1
curr: [1]
i: 2
curr: [1, 2]
i: 3
curr: [1, 3]
i: 4
curr: [1, 4]
i: 2
curr: [2]
i: 3
curr: [2, 3]
i: 4
curr: [2, 4]
i: 3
curr: [3]
i: 4
curr: [3, 4]
i: 4
curr: [4]

Time Complexity: $O(k\cdot {n\choose k})$, similar analysis for all the backtracking problems. k is the length of each new append array we have, we then multiply with worst case combinations we can have, which is ${n\choose k}$.

Space Complexity: $O(k\cdot {n\choose k})$