R5RS中的号码分区

Question

我在实习面试中被问到做了一个创建函数的R5RS程序，我们假设有两个子集。这个函数必须返回#t，如果列表L包含两个元素总数相等且元素个数相同的子集，否则返回#f。它需要输入列表L（只有正数）和一些参数（我认为有用，没有参数数量的条件），所有参数在开始时都等于0。

我仍然记得的要求如下： - 不要定义其他函数并在“two-subsets”函数中调用它们。 - 它只能使用下面的结构：null ?, cond，car，cdr，else，+，=，not，和#t，#f，两个子集（本身用于递归调用），参数的名称如列表，和，等等，数字常量和括号。

有上，我们应该有结果会给出的例子，让我们说：

(two-subsets '(7 7) 0 0 0) returns #t. The two subsets are {7} and {7}. 
(two-subsets '(7 7 1) 0 0) returns #t. The two subsets are {7} and {7}. 
(two-subsets '(5 3 2 4) 0 0) returns #t. The two subsets are {2, 5} and {3, 4}. 
(two-subsets '(1 2 3 6 9) 0 0) returns #f. 

我开始写签名，它看起来对我来说，应该是这样的：

(define two-subsets (lambda (L m n ... other parameters) 
        (cond 

这个问题真的很复杂，它的复杂度显然超过了O（n），我在https://en.wikipedia.org/wiki/Partition_problem上读到它。

我试着从编​​码之前先定义算法开始。我想作为参数：列表L的总和，所以在我的条件下，我只会对总和为< = sum（L）/ 2的组合进行迭代。通过这样做，我可以减少一些问题的复杂性，但我仍然无法弄清楚如何去做。

它看起来像一个有趣的问题，我真的想知道更多关于它。

Answer 1

这是一个不依赖于数字都是正数的版本。我确信，通过了解他们，你可以做得比这更好。

注意这个假设：

• 分区并不需要详尽无遗;
• 但该集合不能为空。

我会很感兴趣的是看到一个版本依赖列表元素+ ve！

(define (two-subsets? l sl sld ssd) 
    ;; l is the list we want to partition 
    ;; sl is how many elements we have eaten from it so far 
    ;; sld is the length difference in the partitions 
    ;; ssd is the sum difference in the partitions 
    (cond [(and (not (= sl 0)) 
       (= sld 0) 
       (= ssd 0)) 
     ;; we have eaten some elements, the differences are zero 
     ;; we are done. 
     #t] 
     [(null? l) 
     ;; out of l, failed 
     #f] 
     ;; this is where I am sure we could be clever about the set containing 
     ;; only positive numbers, but I am too lazy to think 

     [(two-subsets? (cdr l) 
         (+ sl 1) 
         (+ sld 1) 
         (+ ssd (car l))) 
     ;; the left-hand set worked 
     #t] 
     [(two-subsets? (cdr l) 
         (+ sl 1) 
         (- sld 1) 
         (- ssd (car l))) 
     ;; the right-hand set worked 
     #t] 
     [else 
     ;; finally drop the first element of l and try the others 
     (two-subsets? (cdr l) sl sld ssd)]))