We need to solve the PARTITION problem using state-based search.

Problem:

The input is a list L of numbers.

The output is either

(A) a partition of L into two sets U and V such that the sum of the elements in U is equal to the sum of the elements in V (and therefore equal to half the sum of the elements in L) or

(B) no such partition exists

Examples:

If L=[1,4,6,14,17,20], the output could be {1,4,6,20},{14,17}.

If L=[3,4,6,14,17,20], the output is no such partition exists.

Consider the following search solution to this problem:

Let S=the sum of the elements in L.

A state is a triple where R is a list; X and Y are sets; and R, X, and Y form a partition of L.

The start state is .

A goal state is one in which R is the empty list.

The operations on are defined as follows:

Delete the first number in R and try to add it first to X before trying to add it to Y, as long as the sum of the elements in the new set is no more than S/2.

Construct the depth-first search tree to find the first partition (if any) if L=[2,3,6,7] where S=18.

Then answer the following questions:

a. What is the left child of this root node? (X=? Y=?)

b. How many infeasible nodes are tried but pruned ?

c. What is the last infeasible node tried but pruned ? (X=? Y=?)

d. From the root node, go to the left child, then right, then left. This is the L-R-L path. Which node is reached? (X=? Y=?)

e. What goal node is first discoverd (if any) ? (X=? Y=?). Say "None" if no goal node is found.

Extrapolating: Suppose that the list L has size 100.

f. What is the maximum depth of the tree?

A