조합 [DFS]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

풀이 

- nCr 조합 구하기

- for문이 s부터 n까지 돈다. => s~n-1까지 가지가 뻗는다.

 

[예시] 6C4의 첫번째 사이클

s=0 =>  가지는 0부터 5까지 /  L=0 =>  ch[0]=0;

s=1 => 가지는 1부터 5까지 / L=1 => ch[1]=1;

s=2 => 가지는 2부터 5까지 / L=2 => ch[2]=2;

s=3 => 가지는 3부터 5까지 / L=3 => ch[3]=3;

s=4 =>  L이 r과 같다(nCr에서 r만큼 뽑는다.) => 0, 1, 2, 3 출력

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, r;
int ch[20];

//조합
void DFS(int s, int L){
    if(L==r){
        for(int j=0;j<L;j++){
            cout<<ch[j]<<" ";
        }
        cout<<endl;
    }else{
        for(int i=s;i<n;i++){
            ch[L]=i;
            DFS(i+1, L+1);
        }
    }
}

int main(){
    cin>>n>>r;
    DFS(0,0);
    return 0;
}