[LeetCode] #77. Combinations
題目
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
You may return the answer in any order.
直覺解
構想：
用 recursion，basic case 是 k == 2 的時候。跟之前的 18. 4Sum 類似。
python 3 實作（失敗）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
if n < k:
return ans
if n == k:
ans.append([i for i in range(1, n + 1)])
return ans
return self.pick_k((1, n), k)
def pick_k(self, scope, k):
ans = []
if k == 2:
pointer1 = scope[0]
pointer2 = pointer1 + 1
while pointer1 < scope[1]:
if pointer2 < scope[1] + 1:
ans.append([pointer1, pointer2])
pointer2 += 1
else:
pointer1 += 1
pointer2 = pointer1 + 1
return ans
ans = self.pick_k((scope[0]+1, scope[1]), k-1)
for combination in ans:
combination.append(scope[0])
return ans
Submission Detail
Runtime Error Message: RecursionError: maximum recursion depth exceeded in comparison
Input:
2
1
失敗原因
沒考慮到 k 會小於 2
構想：
新增 k == 1 時的處理方式。
python 3 實作（失敗）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
if n < k:
return ans
if n == k:
ans.append([i for i in range(1, n + 1)])
return ans
if k == 1:
for i in range(1, n+1):
ans.append([i])
return ans
return self.pick_k((1, n), k)
def pick_k(self, scope, k):
ans = []
if k == 2:
pointer1 = scope[0]
pointer2 = pointer1 + 1
while pointer1 < scope[1]:
if pointer2 < scope[1] + 1:
ans.append([pointer1, pointer2])
pointer2 += 1
else:
pointer1 += 1
pointer2 = pointer1 + 1
return ans
ans = self.pick_k((scope[0]+1, scope[1]), k-1)
for combination in ans:
combination.append(scope[0])
return ans
Submission Detail
Input:
4
3
Output: [[2,3,1],[2,4,1],[3,4,1]]
Expected: [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]
失敗原因
k > 2 時，只考慮到「包含 scope[0] 的所有組合」，而沒考慮到其他可能的組合
構想：
k > 2 時，要考慮到所有可能的組合。
python 3 實作（失敗）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
if n < k:
return ans
if n == k:
ans.append([i for i in range(1, n + 1)])
return ans
if k == 1:
for i in range(1, n+1):
ans.append([i])
return ans
return self.pick_k((1, n), k)
def pick_k(self, scope, k):
ans = []
if k == 2:
pointer1 = scope[0]
pointer2 = pointer1 + 1
while pointer1 < scope[1]:
if pointer2 < scope[1] + 1:
ans.append([pointer1, pointer2])
pointer2 += 1
else:
pointer1 += 1
pointer2 = pointer1 + 1
return ans
for i in range(0, scope[1]-k+1):
result = self.pick_k((scope[0]+i+1, scope[1]), k-1)
for combination in result:
combination.append(scope[0]+i)
ans.extend(result)
return ans
Submission Detail
Status: Time Limit Exceeded
26 / 27 test cases passed.
Last executed input:
20
16
失敗原因
為了達成 「k > 2 時，要考慮到所有可能的組合，而不是只考慮到包含 scope[0] 的所有組合」，而寫了這行程式碼：
for i in range(0, scope[1]-k+1):
result = self.pick_k((scope[0]+i+1, scope[1]), k-1)但是寫得不好。scope[0] 的值在計算過程中會大於 scope[1]，換句話說，在程序執行過程中，連不可能的組合也考慮進去了。
例如，以 n = 6, k = 4 這組 input 而言，函式的呼叫順序是：
combine(6, 4)pick_k((1, 6), 4)pick_k((2, 6), 3)pick_k((3, 6), 2)pick_k((4, 6), 2)pick_k((5, 6), 2)pick_k((6, 6), 2)pick_k((3, 6), 3)pick_k((4, 6), 2)pick_k((5, 6), 2)pick_k((6, 6), 2)pick_k((7, 6), 2)pick_k((4, 6), 3)pick_k((5, 6), 2)pick_k((6, 6), 2)pick_k((7, 6), 2)pick_k((8, 6), 2)
構想：
暫且還沒想到，如何打從一開始就排除不合理的 scope 範圍，先很暴力地採用「如果 scope 的範圍不合理時，不予計算」的方式。
python 3 實作（成功）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
if n < k:
return ans
if n == k:
ans.append([i for i in range(1, n + 1)])
return ans
if k == 1:
for i in range(1, n+1):
ans.append([i])
return ans
return self.pick_k((1, n), k)
def pick_k(self, scope, k):
ans = []
if scope[1] - scope[0] + 1 < k:
return ans
if k == 2:
pointer1 = scope[0]
pointer2 = pointer1 + 1
while pointer1 < scope[1]:
if pointer2 < scope[1] + 1:
ans.append([pointer1, pointer2])
pointer2 += 1
else:
pointer1 += 1
pointer2 = pointer1 + 1
return ans
for i in range(0, scope[1]-k+1):
result = self.pick_k((scope[0]+i+1, scope[1]), k-1)
for combination in result:
combination.append(scope[0]+i)
ans.extend(result)
return ans
效能：
Runtime: 144 ms, faster than 77.13% of Python3 online submissions for Combinations.
Memory Usage: 15.7 MB, less than 79.42% of Python3 online submissions for Combinations.
研究別人的解
來源：sample 87 ms submission
研究重點：怎麼寫得更簡潔一點、計算速度更快一點。
別人的 python 3 實作（已加上研究用的 print）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
nums = [num for num in range(1, n+1)]
return [ans for ans in self.combination(nums, 0, k, [])]
def combination(self, nums, start, remain, result):
print('<--')
print('nums:', nums, 'start:', start, 'remain:', remain, 'result:', result)
if not remain:
yield result
else:
while len(nums) - start >= remain:
yield from self.combination(nums, start+1, remain-1, result+[nums[start]])
start += 1
print('-->')
效能（沒有加 print 的版本）：
Runtime: 88 ms, faster than 88.88% of Python3 online submissions for Combinations.
Memory Usage: 15.8 MB, less than 52.53% of Python3 online submissions for Combinations.
研究感想
用了 generator，查到的資料說，generator 可以節省計算時間和空間。姑且實驗一下，如果不用 generator 對效能有什麼影響：
class Solution:
def __init__(self):
self.ans = []
def combine(self, n: int, k: int) -> List[List[int]]:
nums = [num for num in range(1, n+1)]
self.combination(nums, 0, k, [])
return self.ans
def combination(self, nums, start, remain, result):
if not remain:
self.ans.append(result)
else:
while len(nums) - start >= remain:
self.combination(nums, start+1, remain-1, result+[nums[start]])
start += 1
效能：
Runtime: 80 ms, faster than 93.34% of Python3 online submissions for Combinations.
Memory Usage: 15.8 MB, less than 52.61% of Python3 online submissions for Combinations.
好吧，從上面這個實驗，暫時看不出來使用 generator 對效能的影響。
對 yield 語法不太熟，目前不確定，他的 combination 函式是什麼時候 return、return 了什麼。姑且做了一些實驗，目前猜測是這樣：
def combination(self, nums, start, remain, result):
if not remain:
yield result
else:
while len(nums) - start >= remain:
yield from self.combination(nums, start+1, remain-1, result+[nums[start]])
start += 1
# 不確定正確的語法怎麼寫，總之是「return 那個 generator」這種感覺。
return yield result
我用 k 紀錄需要挑幾個數字，basic case 分成兩個：，k == 2 時用雙指針挑， k == 1 時做特例處理。他的解答則是利用 remain 紀錄還需要挑幾個數字，並且在「考慮到所有可能性、設定停止條件」這件事上面，他的寫法高明多了：
他的寫法：
while len(nums) - start >= remain:
yield from self.combination(nums, start+1, remain-1, result+[nums[start]])
start += 1
我的寫法：
if scope[1] - scope[0] + 1 < k:
return ans
# 中間省略
for i in range(0, scope[1]-k+1):
result = self.pick_k((scope[0]+i+1, scope[1]), k-1)
for combination in result:
combination.append(scope[0]+i)
ans.extend(result)
我把 for 迴圈的停止條件設定為 range(0, scope[1]-k+1)，因為這個停止條件完全不準確，所以還亡羊補牢地加上 if scope[1] - scope[0] + 1 < k: return ans 強制停止函式，而這個函式考慮的是根本沒有希望的組合，如果可以的話，最好是一開始就不要執行這種沒希望的函式，而不是執行了以後發現他沒希望才強致終止。看了別人的解才發現，自己把「一個 while 迴圈、設定指針」能解決的事情硬生生弄成拖泥帶水的「一個 for 迴圈、一個 if 判斷」，有夠遜的 XD
我主要是操作是雙層 list，所以我還要迭代 list 裡面的個別 list。他主要是操作單層 list，程式碼就少了我的那層迭代 list 的 for 迴圈。
我在 k == 2 時之所以用雙指針，是因為之前的 18. 4Sum 就是用雙指針，直覺就拿來用。看到他的解後，突然明白過來，4Sum 用雙指針為了要快速找到 sum == target 的組合，list 有 sort 過，根據 sum 的值決定指針從兩側網內逼近的方式。但這一題是要把所有組合都列出來，而不是只列出符合特定條件的組合，犯不著出動雙指針。而且用了雙指針，就得再對 k == 1 做特殊處理。
參考資料
研究別人的解
來源：Python by DFS + backtracking [w/ Comment]
別人的 python 3 實作（已加上研究用的 print）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
def gen_comb(n, k, start, cur_comb):
print('n:', n, 'k:', k, 'start:', start, 'cur_comb:', cur_comb)
if k == len(cur_comb):
# base case, also known as stop condition
result.append(cur_comb[::])
return
else:
# general case:
# solve in DFS
for i in range(start, n+1):
cur_comb.append(i)
gen_comb(n, k, i+1, cur_comb)
cur_comb.pop()
return
# ----------------------------------------------
gen_comb(n, k, start=1, cur_comb=[])
return result
效能（沒有加 print 的版本）：
Runtime: 468 ms, faster than 62.10% of Python3 online submissions for Combinations.
Memory Usage: 15.8 MB, less than 22.44% of Python3 online submissions for Combinations.
研究感想
在遞迴過程中，有些 start 的位置，已經沒辦法讓 len(cur_comb) 可以湊到 k 那麼長，可是沒有及時把這個不可能的組合結束掉，所以額外花了很多計算時間。例如，以 n = 13, k = 10 這組 input 為例，在 star 是 5 的時候，就算把 5~13 這些數字都放進 cur_comb 裡，len(cur_comb) 也只有 9 而已，所以 star >= 5 時就該停下來了，但程序依然會繼續計算。
如果搶救一下的話（粗體標示處，不過搶救得很醜就是了⋯⋯）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
def gen_comb(n, k, start, cur_comb):
if k == len(cur_comb):
# base case, also known as stop condition
result.append(cur_comb[::])
return
else:
# general case:
# solve in DFS
for i in range(start, n+1):
if n - (i+1) + 1 < k - (len(cur_comb)+1):
break
cur_comb.append(i)
gen_comb(n, k, i+1, cur_comb)
cur_comb.pop()
return
# ----------------------------------------------
gen_comb(n, k, start=1, cur_comb=[])
return result
效能：
Runtime: 88 ms, faster than 88.70% of Python3 online submissions for Combinations.
Memory Usage: 15.7 MB, less than 79.67% of Python3 online submissions for Combinations.
成功啦！
研究別人的解
來源：Python by DFS + backtracking [w/ Comment]
別人的 python 3 實作（已加上研究用的 print）：
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
results = []
self.dfs(n, k, [], results)
return results
def dfs(self, n, k, curr_combination, combinations):
print('<--')
print('curr_combination:', curr_combination)
print('combinations:', combinations)
if len(curr_combination) == k:
combinations.append(curr_combination.copy())
print('-->')
return
start = curr_combination[-1] + 1 if len(curr_combination) > 0 else 1
remaining_selections = k - len(curr_combination)
end = n - remaining_selections + 1
print('start:', start, 'end:', end)
for num in range(start, end + 1):
curr_combination.append(num)
self.dfs(n, k, curr_combination, combinations)
curr_combination.pop()
print('-->')
效能（沒有加 print 的版本）：
Runtime: 76 ms, faster than 96.25% of Python3 online submissions for Combinations.
Memory Usage: 15.7 MB, less than 79.67% of Python3 online submissions for Combinations.
研究感想
大致構想跟 Python by DFS + backtracking [w/ Comment] 相去不遠，但是 star 和 end 的範圍控制得非常精準，絕對不會計算不可能的組合，從源頭杜絕時間浪費。
原來還可以這樣做啊，每次都對精密計算出 star 和 end 的值，比我那粗暴的搶救方式優雅多了。
Comments
Post a Comment