Backtracking

Elencare i sottoinsiemi

Elencare tutti i sottoinsiemi dell’insieme

void subsets(int n) {
	% Vettore delle scelte
	int[ ] S = new int[1 . . . n]
	subsetsRec(n, S, 1)
}

void subsetsRec(int n, int[ ] S, int i) {
	% S ammissibile dopo n scelte
	if i > n then
		processSolution(S, n)
	else
		% Non presente / presente
		Set C = {0, 1}
		foreach c ∈ C do
			S[i] = c
			subsetsRec(n, S, i + 1)
}

void processSolution(int[ ] S, int n) {
	print "{ "
	for i = 1 to n do
		if S[i] then
			print i, " "
	
	println "}"
}

Complessità: $\mathrm{\Theta }(n\cdot 2^n)$

Elencare le permutazioni

Stampa tutte le permutazioni di un insieme A

void permutations(Set A) {
	int n = size(A)
	int[ ] S = new int[1 . . . n]
	permRec(A, S, 1)
}

void permRec(Set A, Item[ ] S, int i)
	% Se A è vuoto, S è ammissibile
	if A.isEmpty() then
		print S
	else
		% Copia A per il ciclo foreach
		Set C = copy(A)
		foreach c ∈ C do
			S[i] = c
			A.remove(c)
			permRec(A, S, i + 1)
			A.insert(c)
}

Complessità: $O(n^2\cdot n!)$