Yet another case of a weak hypothesis.

We have seen many problems for which induction was used (based on Manber's book) to device an Algorithm for them. However, many times the problem is not easily solved (as is) and it is hard to find the correct hypothesis as well as the correct reduction in size to solve it.

In such cases it is time to rethink the problem and restate it differently. I will use as an example a problem called: "The Balanced Partition problem". In this problem we are given a set of N integers and we are required to answer if the set can be partitioned into two subsets such that their sum is equal. 

Example: {1,5,11,15} can be partitioned into {5,11} and {1,15} and hence the algorithm should return True. On the other hand {1,5,11,14} should return False.

Lets begin with the straight forward induction approach: 

P(1) -> False (we can't divide a set of size 1).

P(2) -> A[0] == A[1].

P(n < N) - Assume that we can solve the problem for n < N elements.

At this point we don't have a "special" element that we can use to reduce the problem's size, as any element contributes equally to the final solution. Lets assume that we ignore the N'th element. Can we use the result of P(N - 1) to solve P(N) ? The answer is No. At least not in the way that we defined our hypothesis. Once we have a result to P(N - 1) we can't extend it to P(N). We need to come up with an alternative induction hypothesis that can be extended in such a way that we can solve our given problem. 

We'll start by noticing that in order for the set to be equally divided into two subsets of equal sum, each of them has to sum to the total set's sum divided by 2. In other words, we can immediately return False in the case that the total sum of our set is not equally divided by 2. 

This hints us as to the new hypothesis:

P(n<N,S) - For a set of n < N elements we return True, if there exists any subset of size S, or False otherwise.

Base cases:

P(1,0) - True (the empty subset).

P(0,S) - False.

How do we extend P(n < N,S) to P(N,S) ? if P(n < N,S) returns True then P(N,S) is also True. However, if P(n < N,S) is False, we still need to check for P(n < N, S - A[N]).

Our final answer will be: P(N,Sum(1,N)/2).

From here the algorithms is straight forward:

The most important part here that I wanted to show in this post is the transformation that I had to do to the hypothesis in order for it to bring me closer to the algorithm. Many times and contrary to intuition, it is better to add constraints to the problem. In this case, I had to add an additional parameter S - the sum in order to be able to solve it.