Equal Product Partition

You are given a list of positive integers. Your task is to determine whether it is possible to partition the list into two non‐empty subsets such that the product of the numbers in one subset is exactly equal to half of the product of all the numbers in the list.

More formally, let the list be nums with n elements. Compute $$T = \prod_{i=1}^{n} nums[i].$$ You need to check if there exists a non‐empty subset \(S\) (and its complement, which is also non‐empty) such that $$\prod_{x\in S} x = \frac{T}{2}.$$

If such a partition exists, output True; otherwise output False.

Note: Since all numbers are positive integers, if \(T\) is odd then such a partition is impossible.

inputFormat

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

• The first line contains an integer \(n\) \( (2 \le n \le 20)\) representing the number of elements.
• The second line contains \(n\) space-separated positive integers.

It is guaranteed that the numbers are small enough so that the product fits in a 64-bit integer.

outputFormat

Output a single line (stdout) containing either True or False (without quotes) indicating whether there exists a partition of the list into two non-empty parts such that one part's product is equal to half of the product of the entire list.

4
1 2 3 6

True