Project Euler Problem 174 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
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.
HackerRank version
HackerRank Project Euler Problem 174:
Python Source Code
N = 250001
count = [0] * N
for n in range(1, int(N**0.5) + 1):
for s in range(n*(n + 1), N, n):
count[s]+= 1
print(sum(0 < c < 11 for c in count[1:]))