R5RS中的数划分

Question

在一次实习面试中，我被要求做一个R5RS程序，创建一个函数，比方说两个子集。这个函数必须返回#t，如果列表L包含两个子集，元素和相等，元素数相等，否则它返回#f。它在条目中接受列表L(仅为正数)和一些参数(我认为这些参数是有用的)。对于参数的数量没有任何条件)，在开始时都等于0。

我仍然记得的需求如下：-不要定义其他函数，并在“两个子集”函数中调用它们。-它只能使用以下构造: null？、cond、car、cdr、+、=、not和#t、#f、两个子集(递归调用本身)、参数的名称，如列表、和、...etc、数字常量和括号。

有几个例子说明了我们应该取得的结果，比如说：

(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)，我在problem上读到了。

我试着先定义算法，然后再对算法进行编码。我考虑把列表L的和作为参数，所以在我的条件下，我只会迭代和为<=和(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)]))