Re: [閒聊] 每日leetcode
: 40. Combination Sum II
昨天官方解答的 backtracking 超不負責任的＝＝
complexity 分析直接給一個 O(2^N)
大哥你 N <= 100 耶 2^100 你不會 TLE 嗎
說要 pruning 結果也只說 target <= 30
2^30 還是跑不過阿
這不就代表跑之前你根本也不知道會不會 TLE
當然有一個上界可以用 integer partition 來限制
https://oeis.org/A000041
https://en.wikipedia.org/wiki/Integer_partition
可以得到 target=30 時答案 list 長度不會超過 5604
（這個上界不是緊的）
又一組解長度 <= 30, 所以遞迴最多只會發生 <20000 次
顯然是秒解的速度
不過我是覺得 如果不能在提交之前就確定不會 TLE
這樣其實不算解出來 因為其實你不知道為什麼能 AC
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723599854.A.F7C.html
推
08/14 09:46,
1年前
, 1F
08/14 09:46, 1F
推
08/14 09:47,
1年前
, 2F
08/14 09:47, 2F
→
08/14 09:48,
1年前
, 3F
08/14 09:48, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 707 之 1548 篇)：