Editing Subset sum problem (section)

=== Inclusion–exclusion ===
The most [[naive solution|naïve algorithm]] would be to cycle through all subsets of ''n'' numbers and, for every one of them, check if the subset sums to the right number. The running time is of order <math>O(2^n \cdot n)</math>, since there are <math>2^n</math> subsets and, to check each subset, we need to sum at most ''n'' elements.

The algorithm can be implemented by [[depth-first search]] of a binary tree: each level in the tree corresponds to an input number; the left branch corresponds to excluding the number from the set, and the right branch corresponds to including the number (hence the name Inclusion-Exclusion). The memory required is <math>O(n)</math>. The run-time can be improved by several heuristics:<ref name=":0" />

* Process the input numbers in descending order.
* If the integers included in a given node exceed the sum of the best subset found so far, the node is pruned.
* If the integers included in a given node, plus all remaining integers, are less than the sum of the best subset found so far, the node is pruned.