这个会有什么复杂度?
如果应用于已排序的列表(升序),
f
简单地按顺序一一列出三元组,使它们的总和小于等于
s
,而不创建重复项或扫描超过第一个太大的元素。
Haskell 代码:
f [] s result = if length result == 3 then [result] else []
f (x:xs) s result
| length result == 3 = [result]
| x + sum result > s = []
| otherwise = f xs s (x:result) ++ f xs s result
输出:
*Main> length $ f [1..300] 300 []
731375
(5.09 secs, 402637784 bytes)
*Main> f [1..10] 13 []
[[3,2,1],[4,2,1],[5,2,1],[6,2,1],[7,2,1],[8,2,1],[9,2,1],[10,2,1],[4,3,1]
,[5,3,1],[6,3,1],[7,3,1],[8,3,1],[9,3,1],[5,4,1],[6,4,1],[7,4,1],[8,4,1]
,[6,5,1],[7,5,1],[4,3,2],[5,3,2],[6,3,2],[7,3,2],[8,3,2],[5,4,2],[6,4,2]
,[7,4,2],[6,5,2],[5,4,3],[6,4,3]]