Given target 't', and a collection of positive integers w1, w2, w3, ..., wn, determine whether there is some selection among the weights so that the total is exactly 't'.
For ex, if t = 10, and the weights are 7, 5, 4, 4, and 1, then the answer is - yes there is selection 5, 4, 1 whose some is '10'
One obvious solution is going through all the subsets of given set of weights, and see if there is any combination that sums up to given total. As we all know set of 'n' elements will have up-to 2^n subsets - which are nothing but no. of combinations. So, the algorithm will be exponential.
Basic gist of the below algorithm is that either item contributes to get to given target 't' or not. So, initially it assumes that the item contributes to get to the given target, and see if rest of the components can contribute to remaining weight. If it is not possible then it checks for the other possibility that the item doesn't contribute to get to the given target, and see if the remaining elements can form the target.
Basically above private method will be invoked by the following public method.
Time ComplexityAnother way to prove that above algorithm is exponential is by considering worst case. Assume that the given target cannot be achieved by the given weights. That means, it essentially go through all combinations which is clearly exponential.
Removing tail recursion
Tail recursion means, at the end of the method typically there will be just recursive call. typically these can be removed either with using a stack or goto statements. Below is the version of removing tail recursion using stack:
"DataStructures and Algorithms" by Aho, Hopcroft, and Ullman http://www.amazon.com/Data-Structures-Algorithms-Alfred-Aho/dp/0201000237)