Subset Sum — Brute Force vs. Modified Greedy

An empirical study of an exact exponential algorithm against a fast 1/2-approximation heuristic on the Subset Sum problem.

---

TL;DR

Two algorithms, same 480 instances, six orders of magnitude apart.

	Brute Force	Modified Greedy
Time complexity	Θ(n · 2ⁿ)	Θ(n log n)
Optimality	Exact	1/2-approximation (provable lower bound)
Empirical growth	1.868ⁿ (R² = 0.9955)	n log n fit, R² = 0.9833
Max tested size	n = 25	n = 100,000
Mean time at n = 25	2.108 s	5.93 µs
Quality ratio (mean)	1.000 (reference)	0.9848
Functional tests	110 / 110 passing	110 / 110 passing

The brute force confirms the worst-case Θ(n · 2ⁿ) bound empirically, and the modified greedy heuristic is — both theoretically and experimentally — a high-quality polynomial-time stand-in.

---

The problem

Given a multiset S of positive integers and a positive target T, find S' ⊆ S maximising sum(S') subject to sum(S') ≤ T.

This is the optimisation form of Subset Sum, one of Karp's 21 NP-complete problems (Karp 1972). It has no known polynomial-time exact algorithm. Applications span budget allocation, financial reconciliation, capacity planning, and the classic Merkle–Hellman knapsack cryptosystem.

---

Algorithms

1. Brute Force — exact baseline

procedure BruteForceSubsetSum(S, T)
    best_sum ← 0;  best_subset ← ∅
    for each subset X of S do            ◀── 2ⁿ subsets
        s ← Σ x∈X x
        if s ≤ T and s > best_sum then
            best_subset ← X;  best_sum ← s
            if best_sum = T then return        ◀── early-exit on exact match
        end if
    end for
    return (best_subset, best_sum)

Implemented as a bitmask enumeration: for mask in range(2**n) where bit i of mask indicates inclusion of S[i]. Inner loop breaks as soon as the running sum overflows T; outer loop breaks as soon as an exact match is found.

The exact-match early exit is what drops the empirical exponential rate from the worst-case 2 down to 1.868 — on random instances at target_ratio = 0.5, exact subset sums are common and the search frequently terminates well before the full enumeration.

2. Modified Greedy — 1/2-approximation

procedure ModifiedGreedySubsetSum(S, T)
    discard elements > T
    sort S descending
    greedy_subset ← ∅;  greedy_sum ← 0
    for each x in S do
        if greedy_sum + x ≤ T then
            greedy_subset ← greedy_subset ∪ {x}
            greedy_sum    ← greedy_sum + x
        end if
    end for
    M ← largest single feasible element       ◀── the fallback
    return  (greedy_subset, greedy_sum)  if greedy_sum ≥ M
            else ({M}, M)

The single-element fallback — return max(greedy_sum, M) — is what gives the algorithm its provable 1/2-approximation guarantee:

Theorem. The modified greedy returns a value A with A ≥ OPT / 2 for every input.

Proof sketch. If greedy adds everything, it's optimal. Otherwise let x be the first skipped element and g the greedy sum at that moment. The skip means g + x > T ≥ OPT. The final output A = max(G, M) ≥ max(g, x) ≥ (g + x) / 2 > OPT / 2. ∎

Without the fallback, the proof can't reach A ≥ x and the 1/2 bound collapses. See docs/report.pdf §3.2.2 for the full proof.

---

Empirical results

Brute force grows like 1.868ⁿ (R² = 0.9955)

A least-squares fit on log₂(T_BF) against n over the measured range n ∈ [2, 25]:

$$\log_2(T_{\mathrm{BF}}) = 0.9018 \cdot n - 22.3286, \quad R^2 = 0.9955$$

$$\Rightarrow T_{\mathrm{BF}}(n) \approx 1.90 \times 10^{-7} \cdot 1.868^n \ \text{seconds}$$

The base 1.868 < 2 is fully accounted for by the early-exit shortcut — many random instances admit an exact subset sum and the enumeration stops early.

Heuristic stays linear-ish at 100,000+ elements

The same instances solved by the modified greedy stay in the single-digit microsecond regime up to n = 25 and reach 0.16 s only at n = 100,000:

At n = 25, brute force is roughly 3.6 × 10⁵× slower than the heuristic on identical inputs. Extrapolating the BF fit to n = 50 gives ~11 days; the heuristic still finishes in microseconds.

Quality of the heuristic

Across 210 quality-comparison instances (n ∈ {5, 8, 10, 12, 14, 16, 18}, 30 runs each), with brute force serving as the ground-truth oracle:

Metric	Value
Mean quality ratio (H / OPT)	0.9848
Minimum observed ratio	0.8307 (at n = 5)
Exact-match rate	13.81 %
Per-size mean ratio	0.974 — 0.994, monotonically improving with n

The heuristic comfortably exceeds the worst-case 1/2 bound; in practice, it lands within ~2 % of optimum on random instances.

Statistical rigour

All 12 heuristic-only sizes (n from 10 to 100,000) satisfy the project rubric's "narrow CI" criterion b/a < 0.1 at the 90 % confidence level, computed via Student-t with 29 degrees of freedom over 30 runs per size.

---

Repository structure

subset-sum-experiments/
├── README.md                    ← you are here
├── LICENSE                      ← MIT
├── requirements.txt
├── src/
│   ├── subset_sum_algorithms.py ← core algorithms + validator + generators
│   ├── run_experiments.py       ← experiment drivers (functional tests + paired BF benchmark)
│   └── main.py                  ← interactive single-instance demo
├── notebook/
│   └── cs301_subset_sum.ipynb   ← fully executed Jupyter notebook (244 KB, 35 cells)
├── docs/
│   ├── report.pdf               ← full project report (45 pages)
│   ├── report.tex               ← LaTeX source
│   └── presentation.pdf         ← 13-slide presentation deck
├── figures/
│   ├── bf_growth_fit.png        ← Figure 12 from the report
│   └── paired_comparison.png    ← Figure 13 from the report
└── data/
    ├── paired_bf_heuristic.csv          ← 480 instances, n ∈ [2,25] × 20 runs
    ├── heuristic_performance_raw.csv    ← 360 measurements, n up to 100k
    ├── heuristic_performance_summary.csv ← per-n mean, std, 90 % CI
    ├── quality_raw.csv                  ← 210 quality measurements
    ├── quality_summary.csv              ← per-n quality summary
    ├── functional_tests.csv             ← 10 hand-crafted unit tests
    ├── randomized_functional_tests.csv  ← 100 randomised property tests
    └── initial_tests.csv                ← 20 sanity-check instances

---

Reproduce the results

# 1. Clone
git clone https://github.com/utkuozgenc/subset-sum-experiments.git
cd subset-sum-experiments

# 2. Install dependencies
pip install -r requirements.txt

# 3. Run the functional tests (10/10 should pass)
cd src && python run_experiments.py

# 4. Try the interactive demo
python main.py

# 5. Regenerate the paired BF/heuristic benchmark (writes to ../data/)
python -c "from run_experiments import run_brute_force_performance; \
           run_brute_force_performance(n_values=range(2,26), runs_per_n=20, seed=42, \
                                       output_path='../data/paired_bf_heuristic.csv')"

The runs are deterministically seeded — output CSVs are bit-identical across machines.

---

Validation summary

Check	Result
Brute force on hand-crafted unit tests	10 / 10 ✅
Modified greedy on randomised oracle tests	100 / 100 ✅
Algorithmic invariants (feasibility, BF dominance, validator agreement)	All preserved ✅
Confidence intervals b/a < 0.1 at 90 % CL	12 / 12 sizes ✅
Quality bound A ≥ OPT / 2	Verified on every instance ✅

---

Background reading

• Karp, R. M. (1972). Reducibility Among Combinatorial Problems — Subset Sum as one of the original 21 NP-complete problems.
• Cormen, T. H. et al. (2009). Introduction to Algorithms, 3rd ed. — Chapters 34–35 (NP-completeness, Subset Sum, FPTAS).
• Ibarra, O. H. & Kim, C. E. (1975). Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. — The classical FPTAS that improves on the 1/2 bound used here.
• Merkle, R. & Hellman, M. (1978). Hiding Information and Signatures in Trapdoor Knapsacks — historical cryptographic application.

---

License

Released under the MIT License. The code, data, figures, and report text are free to read, fork, and reuse with attribution.

---

Citation

If this work was useful to you, you can cite it as:

@misc{ozgenc_pi_kindemir_urasoglu_2026_subset_sum,
  author       = {Pi{\c{s}}kindemir, Ahmet Kaan and {\"O}zgen{\c{c}}, Utku and Uraso{\u{g}}lu, Bora},
  title        = {Subset Sum: Brute Force vs. Modified Greedy --- An Empirical Comparison},
  year         = {2026},
  howpublished = {\url{https://github.com/utkuozgenc/subset-sum-experiments}}
}

---

_{Originally produced as the CS301 — Algorithms term project at Sabancı University, Spring 2025-2026.}