子集總和 - lisp

Question

我正在嘗試在lisp中編寫子集總和問題。 例如：(subsetsum '(1 2 3) 5) = (2 3),(subsetsum '(1 5 3) 2) = nil。

我只能用功能

​​

我能得到任何提示？

Answer 1

此問題的一個簡單的推理如下：

1. 你有一個清單L和一些S
2. 無論是列表的第一個元素是解決方案的一部分，或者它不是
3. 如果第一個是解決方案的一部分，那麼你需要使用它和一個簡單問題的解決方案，如果它不是解決方案的一部分，那麼你需要解決更簡單的問題(rest L) S
4. 有幾種情況下，您可以避免搜索...例如，如果列表爲空，並且S不爲零，或者如果所有元素都大於零，並且將所有元素加起來無法覆蓋S ...