Target Sum Subsets - Dp

medium

1. You are given a number n, representing the count of elements.
2. You are given n numbers.
3. You are given a number "tar".
4. You are required to calculate and print true or false, if there is a subset the elements of which add 
     up to "tar" or not.

Input Format

A number n n1 n2 .. n number of elements A number tar

Output Format

true or false as required

Constraints

1 &lt;= n &lt;= 30
0 &lt;= n1, n2, .. n elements &lt;= 20
0 &lt;= tar &lt;= 50

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

true

Goldmine

Coin Change Combination