[Algorithm] 조합

✔️ '순서' 따위는 없음 , 오로지 몇명을 '다양하게' 뽑을 때 사용 ( 조합 공식 )

 

✔️ 4개 이상을 뽑을 때 - 재귀함수 사용 / 3개 이하 - 중첨 for문 사용 하는 것이 좋다

 

💻 (중요!) 조합을 코드로 구현 (재귀함수 사용)

#include<bits/stdc++.h>
using namespace std;

int n=5; int k=3; //5개 중 3개를 뽑는다
int a[5]={1,2,3,4,5}

void printV(vector<int> v){
	for(int i : v) cout<<i<<" ";
	cout<<"\n";
}

void combi(int start, vector<int> v){
	if(v.size()==k)
	{
		printV(v);
		return;
	}
	
	for(int i=start+1;i<n;i++){
		v.push_back(i);
		combi(i,v);
		v.pop_back();
	}
    return;
}

int main(){
	vector<int> v;
	combi(-1,v);
	return 0;
}

>> 0 1 2
   0 1 3
   0 1 4
   0 2 3
   0 2 4
   0 3 4
   1 2 3
   1 2 4
   1 3 4
   2 3 4

i는 index임

vector v의 size가 3이 될 때 출력이 될 수 있도록 하며 pop_back()이 호출하며 원복된다

 

(코드 도식화)

코드 이해를 위해 도식화를 해보았는데 {0,1,4} 까지는 이해되는데 그 뒤에 {0,2} 부터 이해가 안댐 ㅠ

 

그래서 그림을 다시 그려보면서 이해 완료 

1. combi(1, {0, 1})의 for문은 다 돌았으니(i = 4까지) 이제 combi(1, {0, 1})은 종료될 것임
2. combi(1, {0, 1}) 이 함수를 호출한 combi(0, {0})의 for문의 i=1인 상황으로 옴
3. pop_back( ); 후 vector가 {0} 이 됨. 
4. 계속 이런 식으로 반복

 

💻 조합을 코드로 구현 (중첩 for문 사용)

#include<bits/stdc++.h>
using namespace std;

int n=5; 
int k=3;
int a[5]={1,2,3,4,5};
int main(){
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int k=j+1;k<n;k++){
                cout<<i<<" "<<j<<" "<< k<<"\n";
            }	
        }
    }
    return 0;
}

>> 0 1 2
   0 1 3
   0 1 4
   0 2 3
   0 2 4
   0 3 4
   1 2 3
   1 2 4
   1 3 4
   2 3 4