백준 : 15652 N과 M(4)(C++14)_DFS, 백트레킹

핵심

---

비내림차 순이라는 것은 이전값 보다 크면 안된다는 얘기

구현

---

// 2020-06-23 wsshin

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

void DFS(int n, int m, int nCur);

vector<int> vecOutPutData;
vector<int> vecVisited;

int main()
{
    int n, m;

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        vecVisited.push_back(0);
    }


    DFS(n, m, 0);


    return 0;
}

void DFS(int n, int m, int nCur)
{
    if (nCur >= m)
    {
        for (int i = 0; i < vecOutPutData.size(); i++)
        {
            cout << vecOutPutData[i] << " ";
        }
        cout << "\n";

        return;
    }


    for (int i = 0; i < n; i++)
    {
        if (!vecOutPutData.empty())
        {
            if (i + 1 < vecOutPutData.back()) continue;
        }

        vecOutPutData.push_back(i+1);
        vecVisited[i] = 1;
        DFS(n, m, nCur+1);
        vecVisited[i] = 0;
        vecOutPutData.pop_back();
    }

    return;
}