推 JerryChungYC: 你要回報 08/14 09:46
推 argorok: 有官方解答喔 我以為都是別人分享的== 08/14 09:47
→ Rushia: 官方解很多跑了都tle 後面我都不看了 08/14 09:48
: 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