: 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