Magical Energy Subset Sum

You are given a target magical energy level \(T\) and a collection of \(n\) fruits, each with a certain magical energy value. Your goal is to determine if there exists a non-empty subset of these fruits such that the sum of their energies is exactly equal to \(T\).

More formally, given an integer \(T\) and an array \(E = [e_1, e_2, \dots, e_n]\) of positive integers, determine if there exists a subset \(S \subseteq \{1,2,\ldots,n\}\) with \(S \neq \emptyset\) such that

\(\sum_{i \in S} e_i = T\)

Use a dynamic programming approach to solve this problem efficiently.

inputFormat

The input is given via stdin and has the following format:

1. The first line contains a single integer \(T\) representing the target magical energy.
2. The second line contains a single integer \(n\) indicating the number of fruits.
3. The third line contains \(n\) space-separated positive integers representing the magical energies of each fruit.

outputFormat

Output a single line to stdout containing either True if there exists a non-empty subset whose sum equals \(T\), or False otherwise.

9
6
3 34 4 12 5 2

True