如何编写一个使用 n 和 sum 作为参数的方案程序，并显示所有可以求和的数字（从 1 到 n）？像这样：
（找到 10 10）</p>
((10) (9, 1) (8, 2) (7, 3) (7,2, 1) (6,4) (6, 3, 1) (5, 4, 1) (5, 3, 2) (4 ,3 ,2 ,1))
我找到了一个：
(define (find n sum)
(cond ((<= sum 0) (list '()))
((<= n 0) '())
(else (append
(find (- n 1) sum)
(map (lambda (x) (cons n x))
(find (- n 1) (- sum n)))))))
但它效率低下，我想要一个更好的。谢谢你。
编辑：奥斯卡正确地责备了我不完整的答案。作为忏悔，我提供这个答案，希望能澄清一些事情。
我喜欢 Oscar 对流的使用——我应该作为SRFI-41的作者。但是仅扩展幂集以丢弃大部分结果似乎是解决问题的落后方式。我喜欢 GoZoner 的简单回答，但不喜欢它的低效率。
让我们从 GoZoner 的回答开始，我在下面进行了一些小改动：
(define (fs n s)
(if (or (<= n 0) (<= s 0)) (list)
(append (if (= n s) (list (list n))
(map (lambda (xs) (cons n xs))
(fs (- n 1) (- s n))))
(fs (- n 1) s))))
这会生成一个输出集列表：
> (fs 10 10)
((10) (9 1) (8 2) (7 3) (7 2 1) (6 4) (6 3 1) (5 4 1) (5 3 2) (4 3 2 1))
该函数的一个简单变体产生计数而不是集合列表，这将是本答案其余部分的重点：
(define (f n s)
(if (or (<= s 0) (<= n 0)) 0
(+ (if (= n s) 1
(f (- n 1) (- s n)))
(f (- n 1) s))))
这是该功能的示例运行，包括我古老而缓慢的家用计算机上的计时：
> (f 10 10)
10
> (time (f 100 100)
(time (f 100 ...))
no collections
1254 ms elapsed cpu time
1435 ms elapsed real time
0 bytes allocated
444793
这很慢；尽管对于小输入来说这很好，但评估 是无法容忍的(f 1000 1000)，因为该算法是指数的。问题与朴素斐波那契算法相同；相同的子问题被一次又一次地重新计算。
该问题的一个常见解决方案是记忆化。幸运的是，我们在 Scheme 中编程，这使得将 memoization 封装在一个宏中变得很容易：
(define-syntax define-memoized
(syntax-rules ()
((_ (f args ...) body ...)
(define f
(let ((results (make-hash hash equal? #f 997)))
(lambda (args ...)
(let ((result (results 'lookup (list args ...))))
(or result
(let ((result (begin body ...)))
(results 'insert (list args ...) result)
result)))))))))
我们使用我的Standard Prelude中的哈希表和我博客中的通用哈希函数。那么写函数的memoized版本就很简单了：
(define-memoized (f n s)
(if (or (<= s 0) (<= n 0)) 0
(+ (if (= n s) 1
(f (- n 1) (- s n)))
(f (- n 1) s))))
那不是很漂亮吗？唯一的变化是-memoized在函数的定义中增加了；所有的参数和函数的主体都是一样的。但是性能大大提高：
> (time (f 100 100))
(time (f 100 ...))
no collections
62 ms elapsed cpu time
104 ms elapsed real time
1028376 bytes allocated
444793
这是一个数量级的改进，几乎不费吹灰之力。
但这还不是全部。由于我们知道问题具有“最优子结构”，我们可以使用动态规划。记忆是自上而下工作的，必须暂停当前的递归级别，计算（直接或通过查找）较低级别的解决方案，然后在当前的递归级别恢复计算。另一方面，动态编程是自下而上的，因此子解决方案在需要时总是可用的。这是我们函数的动态编程版本：
(define (f n s)
(let ((fs (make-matrix (+ n 1) (+ s 1) 0)))
(do ((i 1 (+ i 1))) ((< n i))
(do ((j 1 (+ j 1))) ((< s j))
(matrix-set! fs i j
(+ (if (= i j)
1
(matrix-ref fs (- i 1) (max (- j i) 0)))
(matrix-ref fs (- i 1) j)))))
(matrix-ref fs n s)))
我们使用了我的Standard Prelude的矩阵函数。这不仅仅是添加到现有函数，但回报是运行时间的另一个数量级减少：-memoized
> (time (f 100 100))
(time (f 100 ...))
no collections
4 ms elapsed cpu time
4 ms elapsed real time
41624 bytes allocated
444793
> (time (f 1000 1000))
(time (f 1000 ...))
3 collections
649 ms elapsed cpu time, including 103 ms collecting
698 ms elapsed real time, including 132 ms collecting
15982928 bytes allocated, including 10846336 bytes reclaimed
8635565795744155161506
我们已经从 1254 毫秒到 4 毫秒，这是一个相当惊人的改进范围；最终的程序在时间和空间上都是 O( ns )。您可以在以下位置运行该程序http://programmingpraxis.codepad.org/Y70sHPc0，其中包括我博客中的所有库代码。
作为特别奖励，这里是define-memoized宏的另一个版本。它使用 a-lists 而不是哈希表，因此它比上面给出的版本要慢得多，但是当底层计算非常耗时，并且您只想要一种简单的方法来改进它时，这可能正是您所需要的：
(define-syntax define-memoized
(syntax-rules ()
((define-memoized (f arg ...) body ...)
(define f
(let ((cache (list)))
(lambda (arg ...)
(cond ((assoc `(,arg ...) cache) => cdr)
(else (let ((val (begin body ...)))
(set! cache (cons (cons `(,arg ...) val) cache))
val)))))))))
对于刚学习Scheme的人来说，这是一个很好的使用准引号和子句中的=>运算符。cond我不记得我是什么时候写这个函数的——我已经把它放了好几年了——但是当我只需要一个快速而肮脏的记忆并且不关心哈希的时候，它救了我很多次表和通用哈希函数。
您的解决方案通常是正确的，除非您不处理(= n s)此案。这是一个解决方案：
(define (find n s)
(cond ((or (<= s 0) (<= n 0)) '())
(else (append (if (= n s)
(list (list n))
(map (lambda (rest) (cons n rest))
(find (- n 1) (- s n))))
(find (- n 1) s)))))
> (find 10 10)
((10) (9 1) (8 2) (7 3) (7 2 1) (6 4) (6 3 1) (5 4 1) (5 3 2) (4 3 2 1))
我不会声称这特别有效 - 它不是尾递归，也不会记忆结果。这是一个性能结果：
> (time (length (find 100 100)))
running stats for (length (find 100 100)):
10 collections
766 ms elapsed cpu time, including 263 ms collecting
770 ms elapsed real time, including 263 ms collecting
345788912 bytes allocated
444793
>
这与整数划分问题或子集和问题相似，但并不完全相似。这不是整数分区问题，因为整数分区允许重复数字（这里我们只允许范围内的每个数字出现一次）。
虽然它更类似于子集和问题（可以通过动态规划或多或少地有效地解决），但该解决方案需要适应生成所有可能的数字子集，这些子集加到给定数字上，而不是只是该问题的原始公式中的一个子集。可以使用 Scheme 实现动态编程解决方案，但是会有点麻烦，除非使用矩阵库或类似的东西来实现可变表。
这是另一种可能的解决方案，这次生成范围的幂集[1, n]并依次检查每个子集以查看总和是否增加了预期值。不过，这仍然是一种蛮力方法：
; helper procedure for generating a list of numbers in the range [start, end]
(define (range start end)
(let loop ((acc '())
(i end))
(if (< i start)
acc
(loop (cons i acc) (sub1 i)))))
; helper procedure for generating the power set of a given list
(define (powerset set)
(if (null? set)
'(())
(let ((rest (powerset (cdr set))))
(append (map (lambda (element) (cons (car set) element))
rest)
rest))))
; the solution is simple using the above procedures
(define (find n sum)
(filter (lambda (s) (= sum (apply + s)))
(powerset (range 1 n))))
; test it, it works!
(find 10 10)
=> '((1 2 3 4) (1 2 7) (1 3 6) (1 4 5) (1 9) (2 3 5) (2 8) (3 7) (4 6) (10))
更新
前面的解决方案会产生正确的结果，但是它在内存使用方面效率低下，因为它会生成整个幂集列表，即使我们只对其中的一些子集感兴趣。在 Racket Scheme 中，如果我们使用惰性序列，我们可以做得更好，并且只生成需要的值，就像这样（但请注意 - 第一个解决方案仍然更快！）：
; it's the same power set algorithm, but using lazy streams
(define (powerset set)
(if (stream-empty? set)
(stream '())
(let ((rest (powerset (stream-rest set))))
(stream-append
(stream-map (lambda (e) (cons (stream-first set) e))
rest)
rest))))
; same algorithm as before, but using lazy streams
(define (find n sum)
(stream-filter (lambda (s) (= sum (apply + s)))
(powerset (in-range 1 (add1 n)))))
; convert the resulting stream into a list, for displaying purposes
(stream->list (find 10 10))
=> '((1 2 3 4) (1 2 7) (1 3 6) (1 4 5) (1 9) (2 3 5) (2 8) (3 7) (4 6) (10))