lisp - 子集总和 - lisp

Question

我正在尝试用 lisp 编写子集和问题。示例：(subsetsum '(1 2 3) 5)= (2 3)，(subsetsum '(1 5 3) 2)= nil。

我只能使用函数

(atom x) 
(null x)
(eq x y)
(equal x y)
(numberp x)
(append x y)
(car x)
(cdr x)
(cons x y) 
(if x y z)
(cond ... ) 
(let ((x y) (u v)) z)
(let* ((x y) (u v)) z)
(defun ...)
(quote x) and its short form 'x
(list x1 x2 ...)
(print ...)
(sort L fun)

我能得到任何提示吗？

Answer 1

此问题的简化推理如下：

1. 你有一个清单L和一个号码S
2. 列表的第一个元素是解决方案的一部分，或者不是
3. 如果第一个是解决方案的一部分，那么您需要使用它和更简单问题的解决方案(rest L) (- S (first L))
4. 如果它不是解决方案的一部分，那么您需要解决更简单的问题(rest L) S
5. 在某些情况下，您可以避免进行搜索...例如，如果列表为空S且不为零，或者如果所有元素都大于零，甚至将所有元素相加，您无法达到S...