Prolog实现subsum子集和关系代码运行异常求排查提示

原代码问题点 #

• 算术逻辑错误：Prolog 中-是普通中缀运算符，写Sum - X不会自动计算数值差，只会生成结构为-(Sum, X)的复合项，递归到边界条件时，这个复合项永远无法和边界的0匹配，导致无法返回正确结果。
• 缺少必要的数值校验：递归选择元素时没有判断剩余和的合法性，会产生大量无效递归路径。

修改后可运行实现 #

严格遵守仅使用subsum本身作为自定义关系的约束，实现代码如下：

% 边界条件：空集合的唯一子集是空集，元素和为0
subsum([], 0, []).
% 分支1：不选取当前列表的首元素，直接递归处理剩余元素
subsum([_|Xs], Sum, Ys) :-
    subsum(Xs, Sum, Ys).
% 分支2：选取当前列表的首元素加入子集，计算剩余目标和后递归处理剩余元素
subsum([X|Xs], Sum, [X|Ys]) :-
    Sum > 0,
    Rest is Sum - X,
    subsum(Xs, Rest, Ys).

效果验证 #

执行目标查询?- subsum([1,2,5,3,2],5,Sub).将按顺序返回预期结果：

Sub = [1, 2, 2] ;
Sub = [2, 3] ;
Sub = [5] ;
Sub = [3, 2] ;
false.

说明：实现中用到的is和>是Prolog内置算术运算符，不属于自定义关系，符合题目约束。

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