[C++] 백준 15650번 N과 M (2)

https://www.acmicpc.net/problem/15650

풀이 1

재귀함수를 만들어서 N개의 수 중 M개를 고르고, 문자열에 순서대로 저장하여 출력하였다.

재귀함수 solution(int cur, int len, string s) 은
현재 문자열에 추가할 cur, cur을 추가한 후 문자열의 길이 len, 문자열 s를 매개변수로 갖는다.
len이 M일 때, s를 출력한다.
len이 M보다 작을 때, solution(x, len-1, s)를 호출한다. x는 cur 다음 숫자 (cur+1)부터 N이다.

그런데 이 방식은 문제에 1 ≤ M ≤ N ≤ 8 라는 조건이 있기 때문에 가능하다. 만약 N의 최댓값이 10 이상이라면 문자열을 이용하기 어렵다.

코드 1

#include <bits/stdc++.h>

using namespace std;

int N, M;

void solution(int cur, int len, string s) {
    s += cur + '0';

    if(len == M) {
        for(char c : s) cout << c << " ";
        cout << "\n"; 
        return;
    }
    
    for(int i = 1; cur + i <= N; i++) {
        solution(cur + i, len + 1, s);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N >> M;

    string s = "";
    for(int i = 1; i <= N - M + 1; i++) {
        solution(i, 1, s);
    }
    
    return 0;
}

---

풀이 2

vector와 dfs를 이용하여 풀이 1의 단점을 보완하였다.

dfs(int start, int left) 함수는
다음 시작값 start와 남은 개수 left를 이용해서 for 루프의 상한을 N-left+1로 제한하고,
벡터 pick에 값을 추가했다가 해당 분기를 모두 탐색한 후 삭제하였다.

코드 2

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

int N, M;
vector<int> pick;

void dfs(int start, int left) {
    if (left == 0) {
        for (int i = 0; i < pick.size(); i++) {
            cout << pick[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    for (int x = start; x <= N - left + 1; x++) {
        pick.push_back(x);
        dfs(x + 1, left - 1);
        pick.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    pick.reserve(M);

    dfs(1, M);

    return 0;
}