C++ 코딩테스트 Week 00 - 추가

순열과 조합 (vector is already given)

알고리즘 강의에서 주어진 코드는 순열과 조합을 만들 때, 같은 조건하에서 코드를 구성하지 않아 일관성이 떨어짐.

따라서 이미 vector에 오름차순 수열이 주어졌다고 가정한 상황에서 순열과 조합 코드를 작성

암기는 이걸로 하면 될듯

#include <iostream>
#include <vector>
using namespace std;

void makePermutaton(int n, int r, int depth,vector<int> v){
  	//base case
    if(depth==r){
        for(int i:v) cout<<i<<" ";
        cout<<"\n";
        return;
    }
  //branch
    for(int i=depth;i<n;i++){
        swap(v[i],v[depth]);
        makePermutaton(n,r,depth+1,v);
        swap(v[i],v[depth]);
    }
}

void makeCombination(int n,int r,int depth,int start,vector<int> v){
    //base case
    if(depth==r){
        for(int i=0;i<r;i++) cout<<v[i]<<" ";
        cout<<"\n";
      	return;
    }
    //branch
    for(int i=depth;i<n;i++){
        swap(v[i],v[depth]);
        makeCombination(n,r,depth+1,i+1,v);
        swap(v[i],v[depth]);
    }
}


int main(){

    vector<int> v={1,2,3,4};
    cout<<"makePermutaton"<<endl;
    makePermutaton(4,2,0,v);
    cout<<"makeCombination"<<endl;
    makeCombination(4,2,0,1,v);

    return 0;
}

permutation과 combination의 차이 : combination은 이전 원소를 재사용하지 않기 위하여 start 변수를 사용한다.

이외 부분은 두 코드는 동일.