[백준 15650] N과 M (2)

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

문제 분석

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

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

코드

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

int n, m, preNum = 0;
vector<int> vec;
set<vector<int>> _set;

void Backtrack(int start)
{
    if (vec.size() == m)
    {
        _set.insert(vec);
        return;
    }

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

int main()
{
    cin >> n >> m;
    Backtrack(1);
    for (auto v : _set)
    {
        for (auto i : v)
        {
            cout << i << " ";
        }
        cout << endl;
    }
}

해석

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