N과 M(6) - 백준 15655

Problem

< 실버 3 >

백 트래킹, 재귀

---

Soultion

#include <iostream>
#include <vector>
#include <algorithm>
int n, m;
using namespace std;
vector<vector<int>> list;
vector<int> tmp;
void Select(int start, int end, vector<int> v, vector<int> left) {
    if (start == end) {
        list.push_back(v);
        return;
    }
    else {
        if (v.empty()) {
            for (int i = 0; i < left.size(); i++) {
                vector<int> vTmp = v;
                vector<int> vv;
                for (int j = 0; j < i; j++) {
                    vv.push_back(left[j]);
                }
                for (int u = i; u < left.size(); u++) {
                    vv.push_back(left[u]);
                }
                vTmp.push_back(left[i]);
                Select(start + 1, end, vTmp, vv);
            }
        }
        else {
            for (int i = 0; i < left.size(); i++) {
                if (left[i] > v.back()) {
                    vector<int> vTmp = v;
                    vector<int> vv;
                    for (int j = 0; j < i; j++) {
                        vv.push_back(left[j]);
                    }
                    for (int u = i; u < left.size(); u++) {
                        vv.push_back(left[u]);
                    }
                    vTmp.push_back(left[i]);
                    Select(start + 1, end, vTmp, vv);
                }
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        tmp.push_back(a);
    }
    vector<int> blankVector;
    sort(tmp.begin(), tmp.end());
    Select(1, m+1, blankVector, tmp);

    for (vector<int> vv : list) {
        for (int q : vv) {
            cout << q << " ";
        }
        cout << endl;
    }

}

---

Review

1) 입출력 범위 확인

2) empty인 경우를 미리 하고 들어오면 코드가 더 깔끔할 것 같다

예를 들어 메인 함수에서 1~N까지의 호출을 한다던지..?