Haskell如何实现返回目标和数字组合的howSum函数

你的canSum仅返回布尔值标记是否存在可行解，要改造为返回具体组合的howSum，核心是把原来只判断真假的分支逻辑，改为收集可行路径上选中的数字，对应三个核心改造点：

• 递归到target == 0时，不再返回True，而是返回空列表（代表凑出和为0不需要选任何数字，是路径收集的起点）
• 递归到target < 0时，不再返回False，而是返回空值标记当前路径不通
• 遍历数字数组时，不再用any判断是否存在真分支，而是逐个尝试数字：如果减去当前数字的子递归返回了有效组合，就把当前数字拼到组合头部立刻返回；如果当前分支不通就继续尝试下一个数字；所有数字都试不通才返回空值。

基础递归版本（和现有canSum逻辑完全对齐） #

howSum :: Int -> [Int] -> Maybe [Int]
howSum target nums
    | target < 0 = Nothing
    | target == 0 = Just []
    | otherwise = foldr tryBranch Nothing nums
  where
    tryBranch num res
      | Just subComb <- howSum (target - num) nums = Just (num : subComb)
      | otherwise = res

逻辑说明 #

• 用Haskell的Maybe类型对应题目要求的返回规则：Just 组合数组代表存在有效解，Nothing代表不存在解，和你原来canSum的True/False返回逻辑一一对应
• foldr遍历数组的效果和any一致：只要找到第一个可行分支就立刻返回，不会遍历后续多余分支，符合“返回任意有效组合即可”的要求
• 简单测试验证：howSum 7 [2,3]会返回Just [2,2,3]，howSum 7 [2,4]会返回Nothing

性能优化版本（记忆化递归） #

上面的基础版本和你写的canSum一样存在重复计算问题，处理大目标值时效率很低，可以加记忆化缓存已经计算过的target对应的结果，把时间复杂度从O(n^m)降到O(n*m)（n是数字数组长度，m是目标和大小）：

import Data.Map (Map)
import qualified Data.Map as Map

howSum :: Int -> [Int] -> Maybe [Int]
howSum target nums = fst $ memoHow target Map.empty
  where
    memoHow t memo
      | t < 0 = (Nothing, memo)
      | t == 0 = (Just [], memo)
      | Map.member t memo = (memo Map.! t, memo)
      | otherwise =
          let (res, updatedMemo) = foldr tryNum (Nothing, memo) nums
          in (res, Map.insert t res updatedMemo)
      where
        tryNum _ (Just found, curMemo) = (Just found, curMemo)
        tryNum num (Nothing, curMemo) =
          case memoHow (t - num) curMemo of
            (Just subComb, m) -> (Just (num : subComb), m)
            (Nothing, m) -> (Nothing, m)

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