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
- backtracking — A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.
- pruning — Abandoning a branch of a search as soon as a check shows it cannot lead to a valid or better solution.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
Taught in
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers