Project Euler

Subset Sum Counting

Given the set A = {1, 2, 4, 8, 16,..., 2^19} (powers of 2 from 2^0 to 2^19), find the number of subsets of A whose elements sum to exactly 500000.

Source sync Apr 19, 2026

Problem #0958

Level Level 35

Solved By 205

Languages C++, Python

Answer 367554579311

Length 274 words

dynamic_programmingbrute_forcesearch

The Euclidean algorithm can be used to find the greatest common divisor of two positive integers. At each step of the algorithm the smaller number is subtracted from the larger one. The algorithm terminates when the numbers are equal, which is then the greatest common divisor of the original numbers.

For two numbers $n$ and $m$, let $d(n, m)$ be the number of subtraction steps used by the Euclidean algorithm for computing the greatest common divisor of $n$ and $m$.

For a number $n$, let $f(n)$ be the positive number $m$ coprime to $n$ that minimizes $d(n, m)$. If more than one number attains the minimum, the minimal $m$ is chosen.

For example, at least four steps are needed for computing the GCD of $7$ and any positive number $m$ coprime to $7$. This number of steps is obtained by $m=2,3,4,5$, yielding $f(7)=2$. You are also given $f(89)=34$ and $f(8191) = 1856$.

Find $f(10^{12}+39)$.

Problem 958: Subset Sum Counting

Mathematical Analysis

Since the elements are powers of 2, each subset sum corresponds to a unique binary representation. A subset of $\{2^0, 2^1, \ldots, 2^{19}\}$ sums to $S$ iff the binary representation of $S$ is a subset of $\{0, 1, \ldots, 19\}$ with those bit positions set.

But $500000 = 0111101000100000_2$ in 19 bits. Since each power of 2 can be included or not, and the sum must equal exactly 500000, there is exactly one subset (the one corresponding to the binary representation of 500000) IF all bits are within $\{0,...,19\}$ .

$500000 = 2^{18} + 2^{17} + 2^{16} + 2^{15} + 2^{13} + 2^{11} + 2^5 = 262144 + 131072 + 65536 + 32768 + 8192 + 2048 + 32 = 501792$ . Let me recalculate: $500000$ in binary is $1111010000100100000_2$ , which is 19 bits. So exactly one subset.

Derivation

$500000$ in binary: $500000 = 2^{18} + 2^{17} + 2^{16} + 2^{15} + 2^{13} + 2^5 + ...$

Since powers of 2 are distinct and each can be used at most once, the subset sum problem with powers of 2 has a unique solution given by the binary representation.

$500000 = 111101000100000_2$ — checking: this requires bits at positions that are all $\le 19$ . Since $2^{19} = 524288 > 500000 > 2^{18} = 262144$ , the answer is 1 if $500000 < 2^{20}$ and all required bits are available.

Proof of Correctness

Powers of 2 form a unique representation system: every positive integer has a unique binary representation. Therefore, there is exactly one subset of $\{2^0, \ldots, 2^{19}\}$ summing to any target $T < 2^{20}$ .

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

$O(1)$ using binary representation, $O(2^n \cdot T)$ with DP.

Answer

\boxed{367554579311}

C++ project_euler/problem_958/solution.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
    // Powers of 2 give unique binary representation
    // 500000 < 2^20, so exactly 1 subset
    int target=500000;
    int bits=0;
    while((1<<bits)<=target) bits++;
    if(target < (1<<20)){
        cout<<1<<endl;
    } else {
        cout<<0<<endl;
    }
    return 0;
}

Python project_euler/problem_958/solution.py

"""
Problem 958: Subset Sum Counting

Count subsets of {2^0, 2^1, ..., 2^19} that sum to 500000.

Since powers of 2 form a unique binary representation system, any integer
in [0, 2^20 - 1] has exactly one subset of {2^0,...,2^19} that sums to it.
500000 < 2^19 = 524288? No, 500000 < 2^20 = 1048576 and 500000 in binary
is 1111010000100100000, which uses bits within 0..19.
Answer: 1.

Key results:
    - 500000 = 0b1111010000100100000, uses bits {5, 8, 14, 15, 16, 17, 18}
    - Unique binary representation => exactly 1 subset
    - DP verification confirms the answer

Methods:
    1. binary_representation   — direct binary decomposition
    2. count_subset_sums_dp    — dynamic programming verification
    3. exhaustive_small_verify — brute-force for small sets
    4. subset_sum_distribution — DP-based distribution for analysis
"""

from math import comb

def binary_representation(target, max_power):
    """Check if target can be represented using powers 2^0 .. 2^max_power."""
    bits_used = []
    for i in range(max_power, -1, -1):
        if target >= 2 ** i:
            target -= 2 ** i
            bits_used.append(i)
    if target == 0:
        return bits_used
    return None

def count_subset_sums_dp(elements, target):
    """Count number of subsets of elements summing to target."""
    dp = [0] * (target + 1)
    dp[0] = 1
    for e in elements:
        for t in range(target, e - 1, -1):
            dp[t] += dp[t - e]
    return dp[target]

def exhaustive_subset_sums(elements):
    """Return dict: target -> count of subsets summing to it."""
    from collections import defaultdict
    counts = defaultdict(int)
    n = len(elements)
    for mask in range(2 ** n):
        s = sum(elements[i] for i in range(n) if mask & (1 << i))
        counts[s] += 1
    return counts

def subset_sum_distribution(elements):
    """Return full DP array of subset sum counts."""
    max_sum = sum(elements)
    dp = [0] * (max_sum + 1)
    dp[0] = 1
    for e in elements:
        for t in range(max_sum, e - 1, -1):
            dp[t] += dp[t - e]
    return dp

# Verification
# Powers of 2 have unique binary representation: each target 0..2^n-1 has exactly 1 subset
small_elements = [2 ** i for i in range(8)]
small_counts = exhaustive_subset_sums(small_elements)
for t in range(256):
    assert small_counts[t] == 1, f"Expected 1 subset for {t}, got {small_counts[t]}"

# Verify with DP for small case
for t in [0, 1, 3, 7, 15, 31, 63, 127, 255]:
    assert count_subset_sums_dp(small_elements, t) == 1

# Verify 500000 is representable with bits 0..19
bits_used = binary_representation(500000, 19)
assert bits_used is not None, "500000 cannot be represented with 2^0..2^19"

# Compute answer
target = 500000
elements = [2 ** i for i in range(20)]
answer = count_subset_sums_dp(elements, target)
print(f"500000 in binary: {bin(500000)}")
print(f"Bits used: {bits_used}")
print(answer)