Haskell实现：统计列表中和为指定值的子集数量

最近我在练手，想把Python里那个统计列表中和为指定值的子集数量的函数改成Haskell代码，目前已经写了部分实现，先贴出来给大家看看：

test1 :: [Int]
test1 = [2,4,6,10,1,4,5,6,7,8]

countSets1 total input = length [n | n <- subsets $ sort input, sum n == total]
  where
    subsets [] = [[]]
    subsets (x:xs) = map (x:) (subsets xs) ++ subsets xs

countSets2 total input = go (reverse . sort $ input) total
  where
    go [] _ = 0
    go (x:xs) t
      | t == 0 = 1  -- 原代码没写完，这里补了个基础终止条件
      | x > t = go xs t
      | otherwise = go xs (t - x) + go xs t

简单聊下我的思路：

• countSets1 是最直接的写法：先给输入排个序，然后生成所有子集，最后过滤出求和等于total的子集，用length数个数。不过这种方法的问题很明显——子集数量是指数级的，列表长一点性能就拉胯了。
• countSets2 我想优化下，用递归的方式来做：先把列表降序排，然后递归遍历每个元素。如果当前元素比剩下的目标值t还大，直接跳过；不然就分两种情况算——选这个元素（剩下的目标值减它）和不选这个元素，把两种情况的结果加起来。原代码写到一半没完成，我先补了t == 0时返回1的情况，毕竟这时候相当于找到了一个符合条件的组合。

内容的提问来源于stack exchange，提问作者matt