Question

Consider the following problem: given n positive integers, separate them into two groups such that adding all the numbers in one group gives the same result as adding all the numbers in the other group. For example, if the numbers are 1, 2, 3, 4, then the two groups could be {1, 4} and {2, 3}, which both sum to 5. For another example, if the numbers are 5, 6, 11, then the two groups could be {5, 6} and {11}. (The groups do not have to be of the same size).

(a) Describe an exhaustive search algorithm for this problem.

(b) What is the asymptotic worst-case running time of your algorithm? Justify your answer.

Answer 1

Ans 1.

Algo

1. compute total sum of all elements

2. For every item arr[i], we have two choices

    (1) We do not include it first set

    (2) We include it in first set

    We return minimum of two choices

3. If we have reached last element. return two subsets

Ans 2.
All the sums can be generated by either 
(1) including that element in set 1.
(2) without including that element in set 1.
So possible combinations are :-  
arr[0]      (1 or 2)  -> 2 values
arr[1]    (1 or 2)  -> 2 values
.
.
.
arr[n]     (2 or 2)  -> 2 values
So time complexity will be 2*2*..... *2 (For n times),
that is O(2^n).