# Subset Sum (The Subset-Sum Problem)

## Description

Given a set $S$ of integers and a target sum $t$, determine whether there is a subset of $S$ that sum to $t$.

## Parameters

$S$: the set of integers

$n$: the number of integers in the set

$n'$: the number of distinct elements in the set

$t$: the target sum

$\sigma$: sum of elements in the set

## Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Pisinger 2003 $O(nt/logt)$ $O(t/logt)$ Exact Deterministic Time & Space
Faaland 1973 $O(n' t)$ $O(t)$ Exact Deterministic Time & Space
Pferschy 1999 $O(n' t)$ $O(t)$ Exact Deterministic Time & Space
Klinz 1999 $O(σ^{({3}/{2})})$ $O(t)$ Exact Deterministic Time & Space
Eppstein 1997 $\tilde{O}(n max(S))$ $O(t logt)$ Exact Deterministic Time & Space
Serang 2014 $\tilde{O}(n max(S))$ $O(t logt)$ Exact Deterministic Time & Space
Serang 2015 $\tilde{O}(n max(S))$ $O(t logt)$ Exact Deterministic Time & Space
Lokshtanov 2010 $\tilde{O}(n^{3} t)$ $O(n^{2})$ Exact Deterministic Time & Space
Horowitz and Sahni 1974 $O({2}^{(n/{2})})$ $O({2}^{(n/{2})$}) Exact Deterministic Time & Space
Bellman dynamic programming algorithm 1956 $O(n t)$ $O(t)$ Exact Deterministic Time & Space
Psinger 1999 $O(n max(S))$ $O(t)$ Exact Deterministic Time & Space
Koiliaris and Xu 2019 $\tilde{O}(min{\sqrt{n'}t, t^{5/4}, σ})$ $O(t)$ Exact Deterministic Time & Space
Bringman 2017 $\tilde{O}(nt^{1+\epsilon})$ \tilde{O}(nt^\epsilon) (n+t)^{-\Omega(1)} error Randomized Time & Space
Naive algorithm 1940 $O({2}^n * n)$ $O(n)$ Exact Deterministic Space
Random Split Exponential algorithm 1940 $O({2}^{(n/{2})} * n)$ $O({2}^{(n/{2})})$ Exact Deterministic Space

## Reductions FROM Problem

Problem Implication Year Citation Reduction
k-SAT assume: SETH
then: for any $\epsilon > {0}$ there exists a $\delta > {0}$ such that Subset Sum is not in time $O(T^{1-\epsilon}{2}^{\delta n})$, and $k$-Sum is not in time $O(T^{1-\epsilon}n^{\delta k})$