Using CUSP and recursion, re-implement the 2^nd program in homework 1: create a

ID: 3939156 • Letter: U

Question

Using CUSP 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.

Explanation / Answer

void subset_sum(int s0[], int t0[],

int s0_size, int t0_size,

int sum0, int ite0,

int const target_sum0)

{

tot_nodes++;

if( target_sum0 == sum0 )

{

///// found subset

printSubset(t0, t0_size);

///// Exclude previously added item

subset_sum0(s, t0, s0_size, t0_size-1, sum0- s0[ite], ite0 + 1, target_sum0);

return;

}

else

{

///// generate nodes

for( int i = ite0; i < s0_size; i++ )

{

t0[t0_size] = s0[i];

//// next level node (along depth)

subset_sum0(s0, t0, s0_size, t0_size + 1, sum0 + s0[i], i + 1, target_sum0);

}

void generateSubsets(int s0[], int size, int target_sum0)

{

int *tuplet_vector = (int *)malloc(size * sizeof(int));

subset_sum0(s, tuplet_vector, size, 0, 0, 0, target_sum0);

free(tuplet_vector);

}

int main()

{

int weight[] = {10, 7, 5, 18, 12, 20, 15};

int size = ARRAYSIZE(weight);

generateSubsets(weight, size, 35);

printf("Nodes generated %d ", total_nodes);

return 0;