Generation problems

A broad class of competitive programming problems involves generating something, i.e., subsets, or permutations of an existing set. Unlike many problems, the fundamental problem is a complete search problem, i.e., we have to exhaustively clear the search space (as opposed to local search).

Subsets

One good way to generate subsets is with the use of recursion.

From Competitive Programmer’s Handbook:

int n;
vector<vector<int>> sets;
vector<int> subset;
void search(int k) {
	if (k == n) {
		// process subset
	} else {
		search(k+1);
		subset.push_back(k);
		search(k+1);
		subset.pop_back();
	}
}

Permutations

int n;
vector<vector<int>> sets;
vector<int> permutations;
 
void search() {
	if (permutation.size() == n) {
		// process permutation
	} else {
		for (int i = 0; i < n; i++) {
			if (chosen[i]) continue;
			chosen[i] = true;
			permutations.push_back(i);
			search();
			chosen[i] = false;
			permutations.pop_back();
		}
	}
}