Coin Change Possibility

This problem requires you to determine whether it is possible to obtain a target amount using an unlimited supply of coins of given denominations. You are given a list of coin values and an integer amount. Your task is to decide if it is possible to sum up to the given amount using any combination of these coins.

You can solve the problem using dynamic programming. Define a boolean array \(dp\) of size \(amount + 1\) where \(dp[i]\) indicates whether it is possible to form amount \(i\) with the given coins. Initialize \(dp[0] = True\) since a sum of 0 can always be made. For every \(i\) from 1 to \(amount\), set

[ dp[i] = \bigvee_{coin \in coins \text{ and } i \ge coin} dp[i-coin] ]

If \(dp[amount]\) is True, then it is possible to form the target amount; otherwise, it is not.

inputFormat

The input consists of three lines:

1. The first line contains a single integer \(n\), the number of coin denominations.
2. The second line contains \(n\) space-separated integers representing the coin denominations.
3. The third line contains an integer representing the target amount.

outputFormat

Output a single line: "True" if it is possible to form the given amount using the coins, or "False" otherwise.

3
1 2 5
11

True