Intuition
- At each sub-problem, you want to generate all possible combinations at that level, starting from a specific number.
Complexity
Runtime
Space
Code
Backtracking with Optimization
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def bt(arr, start):
arr_len = len(arr)
if arr_len == k:
return [arr.copy()]
need = arr_len - k
avail = n - arr_len
if avail < need:
return []
res = []
for i in range(start, n + 1):
arr.append(i)
res.extend(bt(arr, i + 1))
arr.pop()
return res
return bt([], 1)Backtracking
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def bt(arr, start):
if len(arr) == k:
return [arr.copy()]
res = []
for i in range(start, n + 1):
arr.append(i)
res.extend(bt(arr, i + 1))
arr.pop()
return res
return bt([], 1)NOTE: The following is wrong:
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def bt(arr, start):
if len(arr) == k:
return arr.copy()
res = []
for i in range(start, n + 1):
arr.append(i)
res.append(bt(arr, i + 1))
arr.pop()
return res
return bt([], 1)This is because it leads to a solution which contains an empty array, along with appending a list of lists:
[[[1,2],[1,3],[1,4]],[[2,3],[2,4]],[[3,4]],[]]
MLE
from typing import List
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def r(arr):
if len(arr) == k:
return [arr]
cur = []
for i in range(len(arr)):
tmp = arr.copy()
tmp.pop(i)
cur.extend(r(tmp))
return cur
result = r([i for i in range(1, n + 1)])
# Remove duplicates by converting each combination into a sorted tuple
unique = {tuple(sorted(comb)) for comb in result}
return [list(t) for t in unique]Notes
Cards
START Basic Front: Combinations Back: At each level, consider the starting point END