Assume we have different products () whose prices are respectively, and choose products () from them so that there are no two identical ones. For given two positive integers such that and for each , we want to make , that is, the sum of the prices is between and , by choosing an appropriate combination of products. The following Algorithm 1 implements the backtracking algorithm that is one of the solutions to this problem. In the descriptions of Algorithm 1, represents an empty sequence. In the descriptions of the procedure "back()", the first argument is a sequence of products consisting of the elements of the product set expected to be the solution eventually and the second argument is a set of products that are candidates to be added to the first argument. is the length of the first argument of this "back" invocation. If , the first argument is an empty sequence.
Algorithm 1: Invoke "back()" where the procedure "back" is defined as follows.
Procedure back():
Step 1 Let be a local variable representing a set of products. Initiate with and proceed to Step 2.
Step 2 If , output and terminate. Otherwise proceed to Step 3.
Step 3 If is empty, output the information saying "no solutions" and terminate if , and return to the invoking procedure if . If is not empty proceed to Step 4.
Step 4 Choose one element of , remove it from , and add this element to the end of the sequence . Create the set of whose price satisfies ''. Denote this set by a variable that is different from . Invoke "back()" recursively and go back to Step 3.
Then solve the following questions.
(1) Suppose we execute Algorithm 1 for the four products whose prices are respectively and . The following sequence represents an example of the arguments of the "back" procedure invocations.
Write an example of the arguments of the "back" procedure invocations succeeding to the above ones in the same format in which the execution of a "back" procedure goes back from Step 4 to Step 3 at least one time.
(2) There are some techniques to execute Algorithm 1 efficiently by decreasing the number of invocations of the "back" procedure. One of them is to choose the element of whose price is the highest in Step 4. However, in some cases, this technique does not make the number of invocations the smallest. Show an example of such cases by describing the values of and the arguments of the "back" procedures along the invocations sequence in the same way as (1).
(3) Assume that we invoke "back()" for a sequence of products and a set of products , the number of the elements of is , and is the maximum number of invocations of the "back" procedure during the execution of "back()" where the invocations include the invocation of "back()" itself. Then explain the reason why if .
(4) Describe the maximum number of invocations of the "back" procedures during the execution of Algorithm 1 for products () where the invocations include the invocation of "back()" at the beginning of the execution.