Subset Sum (Can Sum)

You are given a list of integers and a target sum \( S \). Your task is to determine whether there exists a subset of the given list which adds up exactly to \( S \). Each number in the list can be used at most once.

Example:

• For the list [2, 4, 8] and \( S = 6 \), the answer is True because \( 2 + 4 = 6 \).
• For the list [1, 2, 3, 4] and \( S = 11 \), the answer is False since no subset sums to 11.

The problem can be solved using recursion with memoization (or dynamic programming) to efficiently check each combination.

inputFormat

Input is read from stdin and consists of three lines.

• The first line contains an integer \( n \), the number of elements in the list.
• The second line contains \( n \) space-separated integers.
• The third line contains an integer \( S \), the target sum.

outputFormat

Output to stdout a single line with either True or False indicating whether a subset exists that sums exactly to \( S \).

3
2 4 8
6

True