Функция groupSum схемы

Итак, вы спрашиваете, существует ли подмножество данного списка (в позиционном смысле, т.е. сохранение дубликатов, если таковые имеются), которое в сумме дает заданное число.

Прохождение подмножеств — это работа функции powerset, за исключением того, что мы хотим выйти из нее и вернуть #t, как только обнаружим успех. В противном случае просто верните #f в конце.

Дополнение функции powerset из одного из моих других ответов на этом сайте мы получаем

(define (group-adds-to aL aN)
  (call/cc
   (lambda (......)  ;; 2.
     (letrec 
        ([...... (lambda (aL)  ;; 4.
           (cond
             [(empty? aL) (list empty)]
             [else
              (add-into   ;; 5b.
                        (powerset (rest aL))  ;; 3b.
                        (first aL))]))]

         [...... (lambda (r a)  ;; 6.       ; `r` is recursive result, `a` an element
           (cond
             [(empty? r) empty]             ; nothing to add `a` to
             [else
              (cons (add a (first r)) ;; 7. ; either add `a`,
                    (cons (first r)         ;   or not, to the first in `r`
                          (add-into  ;; 5a. ; and recursively proceed
                           (rest r)         ;   to add `a` into the rest of `r`
                           a )))]))]

         [......                      ;; 8.
                  (lambda (......)       ;; 9...
                     (let ([sum ......])   ;; 10...
                       (if (= sum aN)  ;; 11.
                           (return #t)  ;; 1.
                           sum)))])

       (powerset aL)  ;; 3a.
       #f))))   ;; 12.

Заполнить бланки!

Тестирование:

> (group-adds-to '(1 2 5) 7)
#t
> (group-adds-to '(1 2 5) 4)
#f

Требуется несколько тривиальных изменений, чтобы сделать этот #r5rs совместимым, если вам это нужно.

Конечно, этот код можно упростить и сократить, используя больше встроенных функций. Здесь тоже довольно просто избавиться от call/cc. Вы также можете проявить фантазию и добавить проверки для сокращения промежуточных списков, обнаруживая и удаляя такие подгруппы (подмножества), которые никак не могут способствовать успешному результату.

Хорошо, как заполнить пробелы.

1. return? это что?
2. это продолжение побега, созданное для нас call/cc. Когда (if) она вызывается как ;; 1., значение #t сразу же возвращается как окончательный результат всего вызова функции group-adds-to, независимо от того, насколько глубоко внутри рекурсии мы находимся в этот момент. Рекурсия просто прекращается, а результат просто возвращается.
   И если return никогда не вызывался, потому что равенство (= sum aN) ;; 11. так и не было обнаружено, рекурсия завершит свой ход, и #f будет возвращено нормально , как последнее выражение в теле функции, по адресу ;; 12..
3. _а,б powerset? что это?
4. это внутренняя функция, которую мы определили
5. _а,б add-into?
6. это тоже определено здесь.
7. и add?
8. Ага.
9. Сделай сам. Посмотрите, как он используется, в ;; 7, каковы его аргументы, что он должен возвращать.
10. Сделай сам. Ты можешь это сделать!