サブセット生成の2つの方法(インクリメンタル構造法とビットベクトル法)


このアルゴリズムは--劉汝佳のアルゴリズムコンテストの入門経典から来た.本の中で2種類のアルゴリズムの核心コードを紹介して、しかし過程ごとに詳しく解説していないで、また初心者は文字を読む時とても分かりにくいです
問題に直面したら、まず問題の細部を直接研究するのか、それともまず問題をはっきりさせるのか.
細部を先に研究するのではなく、問題をどのように解決するか、方法の枠組みを構築するかを絶対に学ぶべきだと思います.
方法1:考え方:一度に1つの要素を選択して集合に入れる
#include <iostream>
using namespace std;
int a[20];
/*    n       ,  cur     ,   0*/
void print_subset(int n,int* a,int cur){
	for (int i=0;i<cur;i++)//          ,               
		cout<<a[i]<<' ';
	cout<<endl;//    

	//         ,         ,           ,cur > 0, minElem=a[cur-1]+1,   0
	int minElem = cur ? a[cur-1] + 1 : 0;

	//           ,      print_subset(n,a,cur+1),   for  ,
	//                    minElem-n-1。
	//                 (           )
	for (int i=minElem;i<n;i++) {
		a[cur]=i;
		//         
		//cur+1          ,       ,       。
		//         return     ,  i++,a[cur]  (   )  ,        ...
		print_subset(n,a,cur+1);
	}
}

int main(){
	int n ;
	while (cin>>n,n){
		print_subset(n,a,0);
	}
}

方法2:
構想:サブセットA自体を直接構築するのではなく、ビットベクトルb[]を構築する
#include <iostream>
using namespace std;

bool b[20] = {0}; //             
/*    n       ,  b         ,cur     ,   0*/
void print_subset(int n,bool* b,int cur) {
	// cur  n         (   )  
	if(cur == n) {
		for (int i=0;i<n;i++){
			if(b[i])
				cout<<i<<' ';
		}
		cout<<endl;
		return ;
	}
	b[cur] = true;//         
	print_subset(n,b,cur+1);//cur+1            ,     
	b[cur] = false;//          
	print_subset(n,b,cur+1);//cur+1            ,     
}

int main() {
	int n ;
	while (cin>>n,n) {
		print_subset(n,b,0);
	}
}