Project Euler Problem 105 Solution

Project Euler Problem 105 Statement

Let $S(A)$ represent the sum of elements in set $A$ of size $n$. We shall call it a special sum set if for any two non-empty disjoint subsets, $B$ and $C$, the following properties are true:

$S(B) \ne S(C)$; that is, sums of subsets cannot be equal.
If $B$ contains more elements than $C$ then $S(B) \gt S(C)$.

For example, $\{81, 88, 75, 42, 87, 84, 86, 65\}$ is not a special sum set because $65 + 87 + 88 = 75 + 81 + 84$, whereas $\{157, 150, 164, 119, 79, 159, 161, 139, 158\}$ satisfies both rules for all possible subset pair combinations and $S(A) = 1286$.

Using sets.txt (right click and "Save Link/Target As..."), a 4K text file with one-hundred sets containing seven to twelve elements (the two examples given above are the first two sets in the file), identify all the special sum sets, $A_1, A_2, \dots, A_k$, and find the value of $S(A_1) + S(A_2) + \cdots + S(A_k)$.

Solution

HackerRank Project Euler Problem 105 overview:

Determine whether a given set of integers is a special sum set by verifying two conditions: (i) no two non-empty, disjoint subsets have the same sum, and (ii) any subset with more elements has a strictly greater sum than any subset with fewer elements. For each test case, which includes the size of the set and its elements, output "YES" if the set satisfies both conditions, and "NO" otherwise. For example, the set {81, 88, 75, 42, 87, 84, 86, 65} is not a special sum set because there exist disjoint subsets with equal sums, whereas {157, 150, 164, 119, 79, 159, 161, 139, 158} meets both criteria and is considered a special sum set.

Solution Summary

Solution Detail

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 105

HackerRank Project Euler 105: Determine whether or not a set of integers is a "special sum subset."

Python Source Code

from itertools import combinations
def special(q):
    mx = 0
    for i in range(2,len(q)):
        t = set()
        for c in combinations(q,i):
            s = sum(c)
            if s in t or s<=mx: return False
            t.add(s)
        mx=max(t)
    return True

for _ in range(int(input())):
    input()
    s = list(map(int, input().split()))
    print( "YES" if special(s) else "NO" )