Can Sum

You are given a list of integers and a target sum \(T\). Your task is to determine whether it is possible to generate \(T\) by summing any combination of the given numbers. Each number in the list can be used multiple times (including zero times).

One common approach is to use dynamic programming. Define an array \(dp\) of size \(T+1\) where \(dp[i]\) indicates if the sum \(i\) can be reached using the numbers in the array. The recurrence is given by:

\[ dp[i+num] = dp[i] \quad \text{for all } i \text{ where } dp[i] \text{ is true and } i + num \leq T. \]

With the initial condition \(dp[0] = true\), you can iteratively fill in the table and finally check the value of \(dp[T]\).

If \(dp[T]\) is true, output True; otherwise, output False.

inputFormat

The input is read from stdin and consists of three parts:

1. The first line contains an integer n, representing the number of elements in the list.
2. The second line contains n space-separated integers.
3. The third line contains a single integer, the target sum \(T\).

outputFormat

Output a single line to stdout which is True if a combination (with repetition allowed) of the given numbers can sum to \(T\), or False otherwise.

3
2 3 5
8

True