组合递归函数的意外结果

Question

我有一个从特定功率（n）开始的自然数序列，直到从1开始的上限（x）。例如，如果功率为n = 2和x = 5，则该序列为[1, 4, 9, 16, 25]。基于这些数字，我必须找到所有可能的组合，只要集合中1个或多个值的总和返回x。一些例子：

• [[[1,4]]代表x = 5和n = 2]
• [[[1,9]]代表x = 10和n = 2]
• [[[1, 8, 27, 64]]代表x = 100和n = 3]
• 依此类推

我写了以下代码：

combinations :: Int -> [Int] -> [[Int]] -> [[Int]]
combinations t l@(x:xs) a
    | sum l == t  = a ++ [l]
    | otherwise   = (map (x:) (combinations t xs a)) ++ (combinations t xs a)
combinations _ [] a = a

calcPowers x n = filter (<=x) (map (^n) [1..x])

combos x n = combinations x (calcPowers x n) []::[[Int]]

但是返回的结果是：

λ> combos 1 2
[[1]] -- CORRECT
λ> combos 4 2
[[1,4],[4]] -- WRONG
λ> combos 5 2
[[1,4]] -- CORRECT
λ> combos 10 2
[] -- this should be [[1,9]] -- WRONG
λ> combos 100 2
[[1,4,9,16,25,36,49,64,81,100],[1,4,9,16,25,36,49,64,100],.....] -- WRONG
λ> combos 100 3
[[1,8,27,64]] -- CORRECT

知道为什么它不返回正确的序列？

Answer 1

[(map (x:) (combinations t xs a))是不正确的，因为您将在x前面加上，所以组合应与其余部分匹配：

(map (x:) (combinations (t-x) xs a))

在某些时候，t将变为零，并且一个空列表应为该零产生结果。

combinations 0 [] a = []:a
combinations _ [] a = a