Haskell列表拆分问题：如何将正整数列表拆分为等和两部分？

嘿，这个问题我之前也碰到过！咱们一步步来拆解它，搞定这个Haskell函数。

首先得明确核心前提：如果整个列表的总和是奇数，那绝对不可能拆成两个和相等的子列表，这是快速判断失败的关键。如果总和是偶数，那目标就是总和的一半——我们要做的就是按原顺序把元素分配到两个子列表里，直到其中一个子列表的和等于这个目标值。

实现思路 #

1. 前置检查：计算列表总和，若为奇数直接返回Nothing。
2. 回溯+剪枝：用递归遍历每个元素，尝试把它放到第一个子列表（如果不超过目标和），如果这个分支找不到解，再尝试放到第二个子列表。
3. 保持顺序：为了高效添加元素，我们把元素加到列表头部，最后再反转回来，保证子列表的元素顺序和原列表一致。
4. 剪枝优化：如果当前第一个子列表的和加上剩余所有元素的和都达不到目标，直接放弃这个分支，避免无效递归。

完整代码 #

splitEqualSum :: [Int] -> Maybe ([Int], [Int])
splitEqualSum xs = 
    let total = sum xs
        target = total `div` 2
    in if total `mod` 2 /= 0
       then Nothing
       else helper xs [] [] 0 target total
  where
    -- 辅助递归函数：剩余元素、左子列表、右子列表、左和、目标、剩余元素总和
    helper [] left right sumLeft _ _
      | sumLeft == target = Just (reverse left, reverse right)
      | otherwise = Nothing
    helper (x:xs) left right sumLeft target remainingSum
      -- 加到左子列表会超目标，只能加右子列表
      | sumLeft + x > target = helper xs left (x:right) sumLeft target (remainingSum - x)
      -- 剩余元素加起来都凑不够目标，直接剪枝
      | sumLeft + remainingSum < target = Nothing
      -- 先试加左子列表，不行再试右子列表
      | otherwise = case helper xs (x:left) right (sumLeft + x) target (remainingSum - x) of
                      Just result -> Just result
                      Nothing -> helper xs left (x:right) sumLeft target (remainingSum - x)

代码解释 #

• 主函数：先计算总和，判断奇偶性，初始化递归参数。
• 辅助函数：
  • 当没有剩余元素时，检查左子列表的和是否等于目标，是的话返回反转后的两个子列表（因为我们是往头部加元素，反转后恢复原顺序）。
  • 对于每个元素，先判断能不能加左子列表：如果加了会超目标，就直接加右子列表；如果剩余元素的和加当前左和都不够目标，直接返回Nothing。
  • 优先尝试左子列表分支，如果找到解就返回，否则再尝试右子列表分支。

测试示例 #

• 对于你的第一个示例[1,2,3,4,5]，总和是15（奇数），函数返回Nothing，符合预期。
• 对于第二个示例（假设原列表是[1,3,3,4]，总和14，目标7），调用splitEqualSum [1,3,3,4]会返回Just ([1,3,3], [4])；如果是[1,3,4,3]，则会返回Just ([1,3], [4,3])，都满足和相等且元素顺序不变。

小提示 #

这个实现对于短列表很高效，长列表的话因为回溯的特性可能会慢一些，但剪枝已经帮我们减少了很多无效递归。如果要处理非常长的列表，可以考虑用动态规划的方法，但回溯实现更直观，符合Haskell的递归风格。

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