: 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