06 - n개의 원소 중 m개를 고르는 모든 조합을 출력

본격적인 내용에 들어가기 전에 소개한 알고리즘이다. 

 

n개의 원소 중 3개를 고르는 것을 for문으로 작성한다면 3중 for문 형태가 될 것이다.

for(int i=0; i<n-2; i++) {
	for(int j=i+1; j<n-1;j++) {
    	for(int k=j+1; k<n; k++) {
        	~~
        }
    }    
}    

 

4개를 고른다면 4중 for문, 5개를 고른다면 5중 for문의 형태가 될 것인데 이렇게 되면 코드가 너무 복잡하다. 

이 문제를 재귀를 사용해서 해결해 보자.

'원소들의 총 개수', '더 골라야 할 원소들의 개수', '지금까지 고를 원소들 번호' 의 세 개의 매개변수가 필요하다.

 

/* n:전체 원소 수
*  picked: 지금까지 고른 원소 번호
*  topick: 더 골라야 하는 원소 수
*/
void pick(int n, vector<int>& picked, int toPick){
	if(toPick==0){printPicked(picked); return;}
    int smallest = picked.empty() ? 0 : picked.back()+1;
    
    for(int next=smallest; next<n; next++){
    	picked.push_back(next);
        pick(n, picked, toPock-1);
        picked.pop_back();
     }
}

(picked.back()은 벡터의 마지막의 참조를 반환함)