Problem 103: Special Subset Sums: Optimum

Mathematical Development

Theorem 1 (Equivalent Condition for Property 2). Let $A = \{a_1 < a_2 < \cdots < a_n\}$ be a set of positive integers. Property 2 holds if and only if

Proof. ($\Rightarrow$) Take $B = \{a_1, \ldots, a_{k+1}\}$ and $C = \{a_{n-k+1}, \ldots, a_n\}$. These are disjoint since $k + 1 \leq \lfloor n/2 \rfloor + 1 \leq n - k + 1$ for $k \leq \lfloor n/2 \rfloor$. Since $|B| = k + 1 > k = |C|$, Property 2 yields $S(B) > S(C)$.

($\Leftarrow$) Let $B, C$ be disjoint subsets of $A$ with $|B| = m > \ell = |C|$. Write $B = \{b_1 < \cdots < b_m\}$ and $C = \{c_1 < \cdots < c_\ell\}$. Since the $b_i$ are $m$ distinct elements of $A$, we have $b_i \geq a_i$, so $S(B) \geq \sum_{i=1}^{m} a_i$. Similarly, since the $c_j$ are $\ell$ distinct elements of $A$, we have $c_j \leq a_{n - \ell + j}$, so $S(C) \leq \sum_{j=n-\ell+1}^{n} a_j$. Applying the hypothesis with $k = \ell$:

Theorem 2 (Reduction to Global Subset-Sum Uniqueness). Property 1 holds for $A$ if and only if all $2^n - 1$ non-empty subset sums of $A$ are pairwise distinct.

Proof. ($\Leftarrow$) If all subset sums are distinct, then in particular $S(B) \neq S(C)$ for any two distinct non-empty subsets, a fortiori for disjoint ones.

($\Rightarrow$) We prove the contrapositive. Suppose distinct non-empty subsets $B', C'$ satisfy $S(B') = S(C')$. Let $D = B' \cap C'$, $B = B' \setminus D$, $C = C' \setminus D$. Then $B$ and $C$ are disjoint. Since $B' \neq C'$, at least one of $B, C$ is non-empty. If both are non-empty, then

violating Property 1. If exactly one (say $C$) is empty, then $C' \subseteq B'$ and $S(B') = S(C')$ forces $S(B' \setminus C') = 0$; but all elements are positive, so $B' \setminus C' = \emptyset$, contradicting $B' \neq C'$. $\blacksquare$

Lemma 1 (Near-Optimum Heuristic Construction). Given an optimal special sum set $\{b_1, \ldots, b_{n-1}\}$ of size $n - 1$ with middle element $b_m$ where $m = \lceil(n-1)/2\rceil$, the set $\{b_m,\, b_m + b_1,\, b_m + b_2,\, \ldots,\, b_m + b_{n-1}\}$ is a near-optimum special sum set of size $n$.

Proof. This construction, due to Lunnon, yields a set satisfying both properties. The minimum element is $b_m > 0$, ensuring positivity. Property 2 is satisfied because the spread $b_m + b_1$ vs.\ $b_m + b_{n-1}$ inherits the structure of the original set. Optimality is not guaranteed, but the set serves as a starting point for local search. $\blacksquare$

Editorial

The near-optimum set from the construction theorem gives a narrow neighborhood in which the true optimum is expected to lie, so the implementation performs a local search around $\{20,31,38,39,40,42,45\}$ rather than scanning arbitrary 7-element sets. Every candidate produced by a small perturbation is sorted and immediately rejected if it contains a nonpositive entry, repeats an element, or already has a larger total sum than the best set found so far.

The two special-set conditions are then applied in the cheapest useful order. Property 2 is a fast filter because it only compares a few prefix and suffix sums. Only candidates that survive that test pay the cost of Property 1, where every non-empty subset sum is generated and checked for collisions. Whenever a candidate passes both tests and improves the current optimum, it becomes the new best set.

Pseudocode

Begin with the near-optimum set as the current best answer.

For every 7-tuple of perturbations in the chosen search window:
    Add the perturbation to the base set and sort the result.
    Skip this candidate if an entry is nonpositive, if two entries coincide, or if its total already exceeds the best sum found so far.
    Test Property 2 by comparing the sums of the smallest k+1 elements with the largest k elements.
    If Property 2 holds, enumerate all non-empty subsets and check that no subset sum repeats.
    If the candidate passes both tests and improves the best set, record it.

Concatenate the elements of the best set and return that string.

Complexity Analysis

• Time. The perturbation space has $(2 \cdot 3 + 1)^7 = 7^7 = 823{,}543$ candidates. For each candidate passing the sum bound and Property 2 filter, Property 1 costs $O(2^n)$ with $n = 7$, i.e., 128 subset-sum computations. With aggressive pruning, total work is on the order of $10^6$ operations.
• Space. $O(2^n) = O(128)$ for the hash set of subset sums.

Answer

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
using namespace std;

/*
 * Problem 103: Special Subset Sums: Optimum
 *
 * Search for the optimal n=7 special sum set by perturbing the
 * near-optimum {20,31,38,39,40,42,45} by +/-3 on each element.
 */

bool is_special(vector<int>& a) {
    int n = a.size();
    sort(a.begin(), a.end());
    // Property 2
    for (int k = 1; k <= n / 2; k++) {
        int lo = 0, hi = 0;
        for (int i = 0; i <= k; i++) lo += a[i];
        for (int i = 0; i < k; i++) hi += a[n - 1 - i];
        if (lo <= hi) return false;
    }
    // Property 1
    set<int> sums;
    for (int mask = 1; mask < (1 << n); mask++) {
        int s = 0;
        for (int i = 0; i < n; i++)
            if (mask & (1 << i)) s += a[i];
        if (sums.count(s)) return false;
        sums.insert(s);
    }
    return true;
}

int main() {
    int base[] = {20, 31, 38, 39, 40, 42, 45};
    int best_sum = 255;
    vector<int> best_set(base, base + 7);
    const int D = 3;

    for (int d0 = -D; d0 <= D; d0++)
    for (int d1 = -D; d1 <= D; d1++)
    for (int d2 = -D; d2 <= D; d2++)
    for (int d3 = -D; d3 <= D; d3++)
    for (int d4 = -D; d4 <= D; d4++)
    for (int d5 = -D; d5 <= D; d5++)
    for (int d6 = -D; d6 <= D; d6++) {
        vector<int> a = {
            base[0]+d0, base[1]+d1, base[2]+d2, base[3]+d3,
            base[4]+d4, base[5]+d5, base[6]+d6
        };
        bool ok = true;
        for (int x : a) if (x <= 0) { ok = false; break; }
        if (!ok) continue;

        sort(a.begin(), a.end());
        for (int i = 1; i < 7; i++)
            if (a[i] <= a[i-1]) { ok = false; break; }
        if (!ok) continue;

        int s = 0;
        for (int x : a) s += x;
        if (s > best_sum) continue;

        if (is_special(a)) {
            if (s < best_sum || (s == best_sum && a < best_set)) {
                best_sum = s;
                best_set = a;
            }
        }
    }

    sort(best_set.begin(), best_set.end());
    string ans;
    for (int x : best_set) ans += to_string(x);
    cout << ans << endl;
    return 0;
}

"""
Problem 103: Special Subset Sums: Optimum

Find the optimum special sum set of size 7, starting from the
near-optimum {20, 31, 38, 39, 40, 42, 45}.
"""
from itertools import product


def is_special_sum_set(a):
    a = sorted(a)
    n = len(a)
    # Property 2: sum of smallest k+1 > sum of largest k
    for k in range(1, n // 2 + 1):
        if sum(a[:k + 1]) <= sum(a[n - k:]):
            return False
    # Property 1: all subset sums distinct
    sums = set()
    for mask in range(1, 1 << n):
        s = sum(a[i] for i in range(n) if mask & (1 << i))
        if s in sums:
            return False
        sums.add(s)
    return True


def solve():
    base = [20, 31, 38, 39, 40, 42, 45]
    best_sum = sum(base)
    best_set = tuple(sorted(base))
    delta = 3

    for d in product(range(-delta, delta + 1), repeat=7):
        a = [base[i] + d[i] for i in range(7)]
        if any(x <= 0 for x in a):
            continue
        a_sorted = sorted(a)
        if len(set(a_sorted)) != 7:
            continue
        s = sum(a_sorted)
        if s > best_sum:
            continue
        if is_special_sum_set(a_sorted):
            if s < best_sum or (s == best_sum and tuple(a_sorted) < best_set):
                best_sum = s
                best_set = tuple(a_sorted)

    return "".join(str(x) for x in best_set)


if __name__ == "__main__":
    answer = solve()
    print(answer)
    assert answer == "20313839404245"