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)]))