8 Aug 2020

순열,조합 구현하기 [c++]

조합

n개 중에 m개를 골라라(순서에 상관 없이) > 집합의 개념

ex) 1,2,3 일때

1,2
1,3
2,3

코드

int n,m;
vector<int> arr;

void print(vector<int> picked){
    for(auto pick:picked){
        cout<<pick<<" ";
    }
    cout<<'\n';
}

void dfs(vector<int> picked,int idx){
    if(picked.size()==m){
        print(picked);
        return;
    }
    for(int i=idx;i<n;i++){
        picked.push_back(arr[i]);
        dfs(picked,i+1);
        picked.pop_back();
    }
}

void input(){
    cin>>n>>m;
    arr.resize(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
}

void solution(){
    vector<int> temp;
    input();
    dfs(temp,0);
}

int main(){
    solution();
}

결과

순열

n개 중에 m개를 골라 줄 세우는것 (순서를 고려한다)

ex) 1,2,3 일때

1,2
1,3
2,1
2,3
3,1
3,2

코드

int n,m;
vector<int> arr;
vector<bool> visited;
void print(vector<int> picked){
    for(auto pick:picked){
        cout<<pick<<" ";
    }
    cout<<'\n';
}

void dfs(vector<int> picked){
    if(picked.size()==m){
        print(picked);
        return;
    }

    for(int i=0;i<n;i++){
        if(!visited[i]){
            visited[i]=true;
            picked.push_back(arr[i]);
            dfs(picked);
            picked.pop_back();
            visited[i]=false;
        }
    }
}
void input(){
    cin>>n>>m;
    arr.resize(n);
    visited.resize(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
}

void solution(){
    vector<int> temp;
    input();
    dfs(temp);
}

int main(){
    solution();
}

결과

Tags:

0 comments