N과M (5)

코드

[ 백트래킹 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M, input;
int arr[10];
bool isused[10];
vector<int> save(10);
void func(int depth){
    if(depth == M){
        for(int i=0;i<M;i++)
            cout << arr[i] << ' ';
        cout << '\n';
    }else{
        for(int i=0;i<N;i++)
        {
            if(isused[i]) continue;
            isused[i] = true;
            arr[depth] = save[i];
            func(depth+1);
            isused[i] = false;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        cin >> save[i];
    sort(save.begin(), save.begin()+N);
    func(0);
    return 0;
}

• 수가 정해져 있기 때문에 save 변수를 쓰는데, 사전순 증가로 출력해야 하기 때문에 정렬하려고 vector<int> save로 선언

---

[ next_permutation 코드 ]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
int arr[10];
vector<int> save(10);
vector<vector<int>> ans;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        cin >> save[i];
    sort(save.begin(), save.begin()+N);
    fill(arr, arr+N, 1);
    for(int i=0;i<M;i++) arr[i] = 0;    

    do{
        /* 1) 조합으로 뽑은 숫자를 tmp에 저장
           2) tmp에 대해 next_permutation() 수행 */
        vector<int> tmp;
        for(int i=0;i<N;i++)
            if(!arr[i]) tmp.push_back(save[i]);
        do{
            ans.push_back(tmp);
        }while(next_permutation(tmp.begin(), tmp.end()));
    }while(next_permutation(arr, arr+N));

    /* 제일 앞 요소가 작은 순서대로 오름차순 정렬 */
    sort(ans.begin(), ans.end());
    /* 2중 for문으로 출력 */
    for(auto a : ans)
    {
        for(auto b : a)
            cout << b << ' ';
        cout << '\n';
    }
    return 0;
}

• next_permutation()을 2중으로 써야함
  1) 전체 N개에서 M개를 뽑은 숫자들 구하는 do~while
  2) 뽑은 M개 숫자에 대해 다시 경우의 수를 구하는 do~while

• vector<vector<int>> ans에 대해 오름차순 정렬하면
  요소별로 비교해서 정렬됨!