Count number of subsets with given sum

The Memoization Technique is basically an extension to the recursive approach so that we can overcome the problem of calculating redundant cases and thus decrease time complexity.

We can see that in each recursive call only the value of "n" and "sum" changes, so we can store and reuse the result of a function(..n, sum..) call using a "n * sum" 2-D array.

The 2-D array will store a particular state (n, sum) if we get it the first time.

Now, if we come across the same state (n, w) again, instead of calculating it in exponential complexity, we can directly return its result stored in the table in constant time.

The time complexity of this solution is (n * sum).

In addition, O(n * w) auxiliary space was used by the table and O(n) by call stack.

Count number of subsets with given sum is a variation of the 0/1 knapsack and the subset sum problem.

The idea of the recursive approach is to consider all subsets of items and find whether there exists a subset whose sum equals "sum".

While considering an item, we have one of the following two choices:

Choice 1: The item is included in the optimal subset—decrease the sum by the item value.
Choice 2: The item is not included in the optimal set—don't do anything.

While picking an element, also make sure that the value of the item is less than or equal to the remaining "sum".

If sum is exhausted (equals to "0"), then return "1" and if array is exhausted (n equals to "0"), return "0".

If the current element is less than the remaining "sum," return the sum of the results of recursive calls (one including and one excluding the current element).

The above recursive function computes the same sub-problems again and again.

The time complexity of this solution is exponential (2^n).

In addition, O(n) auxiliary stack space was used for the recursion stack.