# Subset Sum

Given an array of size **n** and a sum **K**, determine whether any subset is possible with that sum or not. Print **"yes"** if there is any subset present else print **"no"**.

Input & output:
In the first line the input will be n and K, space separated.
The next line contains the array elements
Output will be "yes" or "no"

**Example with explanation:**

**Example 1:**

Input:
The array size be: 5
The sum be: 11
The Elements be: 5 6 7 3 9
Output:
Yes
Explanation:
5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".

**Example 2:**

Input:
The array size be: 5
The sum be: 11
The Elements be: 5 6 7 3 9
Output:
Yes
Explanation:
5 & 6 sums to 11. Thus the subset can be [5, 6] and output will be "yes".

Of course the naïve solution would be to generate all possible subsets and check their sum equals to

Kor not. But it would of course be computationally exponential to generate all possible subsets.To do so, the recursion would be:

For nth element the cases are:

So, the recursion function can be written as:

Where,

Now base case would be,

Here comes the concept of sub problem. Initially the problem is for size n and sum K. Then it gets reduced to

{size (n-1) and sum K} or {size (n-1) and (sum K-arr[n-1])}So if you draw the recursion tree there will be many such sub-problem which will be overlapping ones. That means we will re-compute same sub-problems again and again. That’s why we need to store the value of sub-problems and use dynamic programming.

Converting to dynamic programming:C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput