Can Sum: Unbounded Subset Sum Problem

You are given a list of positive integers and a target sum. Your task is to determine whether it is possible to generate the target sum by summing any combination of the numbers in the list. You can use each number in the list an unlimited number of times.

Note: The sum is computed using the formula:

[ dp[i] = \bigvee_{num \in arr,\ i-num \ge 0}dp[i-num] ]

with the base condition being \(dp[0] = True\). If \(dp[target]\) evaluates to True, then a combination exists that adds up to the target value; otherwise, it does not.

inputFormat

The input is read from standard input (stdin). It consists of two lines:

• The first line contains two integers \(n\) and \(target\) separated by a space, where \(n\) is the number of elements in the list.
• The second line contains \(n\) space-separated positive integers representing the elements of the list. If \(n = 0\), the second line will be empty.

outputFormat

Output to standard output (stdout) a single line containing either True or False (case-sensitive) representing whether a combination exists that sums up to the target.

4 11
2 3 7 8

True