Combinatorics

Generating Subsets

I really struggled with this problem. I remember for the Citadel online assessment, this was part of the problem and I really had no idea how to do it.

Number of different Subsets $\to$ use $2^n-1$

Method 1

Use recursion

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

Method 2

Use bit representation of integers. ?

Related

• Permutations
• Geometric Series