Complete search: enumerating candidate solutions · 3 of 3
Subsets and permutations
Loop over every subset with a bit mask and over every ordering with the library, without counting a repeated string twice.
Books1
Links4
- Complete Search with Recursion Apple Division solved by recursion and by bit masks, and Creating Strings by recursion and with the library, followed by practice problems. usaco.guide (opens in a new tab)
- itertools.permutations States the order in which the tuples come out, and that two elements in different positions count as different even when their values are equal. docs.python.org (opens in a new tab)
- std::next_permutation What the return value means, the bound of at most n/2 swaps per call, and a possible implementation of the step to the next arrangement. en.cppreference.com (opens in a new tab)
- Algorithms, Chapter 2: Backtracking Section 2.3 solves Subset Sum by recursion, deciding for one element at a time whether it is in the subset, and counts the calls with a binary tree. Parts of this page adapt this chapter's text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code. jeffe.cs.illinois.edu (opens in a new tab)