subset sum

The problem of deciding whether some subset of a list of numbers adds up exactly to a target value.

In more detail

Each number is either in or out, so there are 2^n subsets to consider. Backtracking prunes a branch as soon as its running total exceeds the target, and the course measures how many nodes that saves. For small integer targets, dynamic programming solves it in O(n × target).

Related terms

Taught in

References