Leetcode # 77. Combinations

https://leetcode.com/problems/combinations

Solution (Backtracking)

\begin{align}
&\text{Time Complexity: }O(k \cdot \text{C}^n_k)\\
&\text{Space Complexity: }O(k)\\
\end{align}

1. _combine([1, 2, …, n – 1], k) 使用O(Cⁿ_k) 的 time complexity
   之後分支的每一層所使用的 time complexity 越來越少
   (_combine([1, 2, …, n – 1], k) → _combine([2, 3, …, n – 1], k) → _combine([3, 4, …, n – 1], k) → … )
   time complexity 的上限為 k * O(Cⁿ_k) = O(k * Cⁿ_k) = n! / [(k – 1)! * (n – k)!]
2. 因為 output 所使用的空間不計入 space complexity
   所以只有 recursion 使用的 O(k)
   （recursion call stack 的最大 depth 為 k）

class Solution:
  def combine(self, n: int, k: int) -> List[List[int]]:
    def _combine(l, k):
      if k == 1:
        return [[e] for e in l]
      if k > len(l):
        return []
      
      return _combine(l[1:], k) + [[l[0]] + _l for _l in _combine(l[1:], k - 1)]
    return _combine([i for i in range(1, n + 1)], k)

Solution (Queue)

Time Complexity: O(Cⁿ_k)
（加了 if n - cur[-1] + 1 < k - len(cur): continue 
能排除掉剩餘數字已不夠構築長度為 k 的組合，大幅提升速度）
Space Complexity: O(k ** 2)
（每一輪的 queue 的最大 space complexity 為 len(cur) * (k – len(cur) + 1)
len(cur) 為 k / 2 時有最大值 (k / 2) * (k – k / 2 + 1) = (k ** 2) / 4 + (k / 2)）
(The input and output generally do not count towards the space complexity.)

class Solution:
  def combine(self, n: int, k: int) -> List[List[int]]:
    queue = collections.deque([[i] for i in range(1, n + 1)])
    all_possible_combinations = []
    while queue:
      cur = queue.popleft()
      if len(cur) == k:
        all_possible_combinations.append(cur)
        continue
      if n - cur[-1] + 1 < k - len(cur): continue
      for i in range(cur[-1] + 1, n + 1):
        queue.append(cur + [i])

    return all_possible_combinations

Last Updated on 2023/08/16 by A1go