Subset Sum Problem

You are given a set of n integers (weights) and a target integer \(k\). Your task is to determine if there exists a subset of these integers that sums exactly to \(k\). Note that the empty subset is allowed and its sum is considered to be \(0\).

This problem can be efficiently solved using dynamic programming. One common approach is to use a 1-dimensional DP array \(dp\) where \(dp[i]\) is true if there exists a subset of the given weights that sums to \(i\). The recurrence is described by:

[ \text{dp}[j] = \text{dp}[j] \lor \text{dp}[j - w]\quad \text{for each weight } w \text{ and } j \text{ from } k \text{ down to } w. ]

Good luck!

inputFormat

The input is read from standard input (stdin). The first line contains two integers (n) and (k), where (n) is the number of items and (k) is the target sum. The second line contains (n) space-separated integers representing the weights.

outputFormat

Output a single line to standard output (stdout) with the string "Possible" if there exists a subset that sums to (k), or "Not Possible" otherwise.## sample

5 9
1 2 3 4 5

Possible