The third homework includes Using CLISP and recursion reimpl

The third homework includes: Using CLISP and recursion, re-implement the 2^nd program in homework 1: create a list or an array of random integers (e.g., between [0. 50]) and a target number (e.g., 60), then find all subsets of the integers of the list/array such that the numbers in each subsets add up to the target number. Note that besides printing the numbers of each subset, you also need to print the original indices of the numbers. For example, given array A = {5, 3, 4. 2. 6. 7}. target = 9, the number pairs are (5. 4), (3. 6), (2, 7), and (3, 4. 2). Their indices are (0. 2), (1, 4), (3, 5), and (1, 2, 3), respectively. Compare the difference between sorting array and sorting list in Lisp

Solution

LISP is a functional programming language in which every each unit is a function. Hence the subset sum problem can be solved by using the recursion functions:

(defun subset-sum (set sum &optional subset)

(when set

(destructuting-bind (head . tail) set

( or ( and (=head sum) (cons head subset))

( subset-sum tail sum subs

( subset-sum tail (- sum head) (cons head subset))))))

the above LISP program is used to solve the subset sum problem. The basic difference between sorting array and sorting list is that list sorting is more efficient than array sorting. There are two methods sort and stable-sort that are used for sorting the list or array.