[boj][c++] N과 M (2) (15650)

문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.

내 풀이 방법 : 재귀 사용

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

int n, m;

void backtrack(int num, int cnt, string res){
    if(cnt == 0){ //카운트가 0이면 숫자 다 뽑았으므로 출력
        cout << res << '\n';
        return;
    }
    //새로운 숫자(num ~ i)까지 한 번씩 뽑기
    for(int i=num; i<=n; i++){
        string tmp_res = res;
        tmp_res += to_string(i);
        tmp_res += " ";
        backtrack(i + 1, cnt-1, tmp_res); //뽑아서 res에 추가해 저장
    }

}

int main(){
    cin >> n >> m;
    backtrack(1, m, "");
}

재귀 함수를 사용하여 res에 그동안 방문한 값들을 저장하였다.

숫자가 커질 경우 메모리 사용량이 커질 수 있기 때문에 vector에 저장하여 가지고 다니는 방법을 떠올렸다.

 

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

int n, m;

vector<int> v;
bool visited[9];

void backtrack(int num){
    if(v.size() == m){
        for(int i=0; i<v.size(); i++) cout << v[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i=num; i<=n; i++){
        if(!visited[i]){
            visited[i] = 1;
            v.push_back(i);
            backtrack(i + 1);
            v.pop_back();
            visited[i] = 0;
        }   
    }
}

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

v와 visited 벡터를 이용해 저장된 값을 확인하였다.