Subset Sum

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

Related Problems

Subset Sum

Dynamic Subset Sum

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 14 of 14 algorithms

				See more
Koiliaris and Xu	2019	$\tilde{O}(\min(\sqrt{n'}t, t^{5/4}, \sigma))$	$O(t)$
Bringman	2017	$\tilde{O}(nt^{1+\epsilon})$	$\tilde{O}(nt^{\epsilon})$
Serang	2015	$\tilde{O}(n \max(S))$	$O(t\log t)$
Serang	2014	$\tilde{O}(n \max(S))$	$O(t\log t)$
Lokshtanov	2010	$\tilde{O}(n^3 t)$	$O(n^2)$
Pisinger	2003	$O(nt/\log t)$	$O(t/\log t)$
Pferschy	1999	$O(n' t)$	$O(t)$
Klinz	1999	$O(\sigma^{3/2})$	$O(t)$
Psinger	1999	$O(n \max(S))$	$O(t)$
Eppstein	1997	$\tilde{O}(n \max(S))$	$O(t\log t)$
Horowitz and Sahni	1974	$O(2^{(n/2)} n)$	$O(2^{n/2})$
Faaland	1973	$O(n' t)$	$O(t)$
Bellman dynamic programming algorithm	1956	$O(nt)$	$O(t)$
Naive algorithm	1940	$O(n 2^n)$	$O(n)$

Reductions Table

Displaying 1 of 1 reductions

Other relevant algorithms

Insuffient Data to display table