Un insieme di N elementi ha 2^N (2 alla N) sottoinsiemi; difatti puoi mettere tali insiemi in corrispondenza biunivoca con l'insieme delle stringhe binarie di lunghezza N, proprio nel modo fatto dall'algoritmo che associa ogni generico sottoinsieme ad una generica sequenza di zeri ed uni, tale che sol[k] == 1 sse il k-esimo elemento appartiene al sottoinsieme.

Ora, per costruire un sottoinsieme quello che devi fare è passare in rassegna tutti gli eleemnti, e per ciascuno decidere se considerarlo o non considerarlo. In particolare, supponi di aver gàa considerato i primi k elementi, ora ti tocca decidere se prendere o meno il k+1-esimo elemento, cioè decidere se porre sol[k+1]=0 o sol[k+]=1; dopodichè continui col k+2-esimo elemento, ovvero ripeti la procedura incrementando k; quando k == N significa che hai preso una decisione su tutti gli elementi, e quindi puoi stampare il sottoinsieme.

Nel caso del tuo algoritmo non vuoi solo creare un generico sottoinsieme, ma li vuoi stampare tutti, quindi, quando consideri il generico elemento k, prima poni sol[k]=0, scartando cosi k dal sottoinsieme, e ciò ti permette di costruire tutti i sottoinsiemi che non hanno k; poi richiami la proceduira ricorsivamente anche con sol[k]=1, in modo da poter costruire tutti i sottoinsiemi che hanno k.

Costurire questi sottoinsiemi è come costruire tutte le stringhe binarie di lunghezza N che sono proprio 2^N, e difatti ogni chiamata ricorsiva si dirama in due sottochiamate, cosi alla fine si avranno 2^N chiamate ricorsive.