[백준 15652] N과 M (4)

🔗문제 풀러가기
단계별로 풀어보기 단계 22의 4번째 문제이다.

문제 분석

백트래킹 알고리즘을 이용하여 문제를 해결하였다.

백트레킹?
백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법.
최적화 문제와 결정 문제를 푸는 방법이 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> vec;

void Backtrack(int start)
{
    if (vec.size() == m)
    {
        sort(vec.begin(), vec.end());
        for (auto i : vec)
        {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = start; i <= n; i++)
    {
        vec.push_back(i);
        Backtrack(i);
        vec.pop_back();
    }
}

int main()
{
    cin >> n >> m;
    Backtrack(1);
}

해석

1. n과 m을 입력받아 Backtrack을 1부터 실행한다.
2. 만약 벡터의 사이즈가 m이 된다면 벡터를 정렬한 후, 모든 요소를 출력한다.
3. 그렇지 않다면 매개변수로 들어온 start에서부터 n까지 for문을 돌며 벡터에 i를 저장한 후, Backtrack(i)을 하여 i부터 n까지의 모든 수를 재귀해 출력한다. 재귀가 끝난다면 벡터에서 요소를 제거한다.