2장. 프로그래밍 기법 (2.2 재귀적 알고리즘), Recursion

2.2.1 부분집합 생성하기

 

vector <int > subset;
void search(int k){
	if(k == n+1){
    	//부분집합을 구한 상태임.
    }
    else{
    	//k를 부분집합에 포함시킨다.
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
        //k를 부분집합에 포함시키지 않는다.
        search(k+1);
    }
}

 

 

2.2.2 순열 생성하기

vector <int> permutation;
bool chosen[n+1];

void search(){
	if(permutation.size() == n){
    	//순열을 만든 상태임
    }
   	else{
    	for(int i = 1; i <= n; i ++){
        	if(chosen[i]) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back(i);
        }
    }
}

C++ 표준 라이브러리 next_permutation사용하기

for(int i = 1; i <=n; i ++){
	permutation.push_back(i);
}

do{
	//
}while(next_permutation(permutation.begin(), permutation.end());