Back Tracking 15650

1
//1번과 다른 점 - i보다 작은것은 출력되지 않음 즉,오름차순
2
//이전에 선택한 숫자보다 큰 숫자만 출력해야함
3

4
#include <bits/stdc++.h>
5
#define fIO ios_base::sync_with_stdio(false); \
6
cin.tie(NULL);
7
using namespace std;
8

9
vector<int> answer;
10
vector<bool> check;
11
int n, m;
12
void recursion(int m, int count, int index)    // 뽑아야 할 숫자의 개수, 지금까지 뽑은 숫자의 개수(현재 수열의 길이)
13
{                                              // 중복을 피하고 나보다 높은 숫자만 고르도록
14
    if(count == m)    //m개를 다 선택했다면 출력
15
    {
16
        for(int i = 0; i < m; i++)
17
        {
18
            cout << answer[i] << " ";
19
        }
20
        cout << "\n";
21
        return;
22
    }
23

24
    for(int i = index; i <= n; i++)
25
    {
26
        if(!check[i])
27
        {
28
            check[i] = true;
29
            answer.push_back(i);     // i번쨰 선택
30
            recursion(m, count + 1, i+1); // i로 시작하는 경우들 탐색끝내고 돌아옴
31
            check[i] = false;
32
            answer.pop_back();       // i선택 취소
33
        }
34
    }
35
}
36

37
int main()
38
{
39
    fIO
40
    cin >> n >> m;
41
    check.resize(n+1, false);
42
    recursion(m, 0, 1);
43

44
    return 0;
45
}