[BOJ] 백준 15651. N과 M (3)

▶문제설명

[BOJ] 백준 15651. N과 M (3)

https://www.acmicpc.net/problem/15651

▶ 설계

---

[문제]

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

문제에서 N과 M (1)과 다른점은 진한 글씨로 표시된 부분 밖에 없습니다.

N과 M(1) 풀이 링크 ( https://it-earth.tistory.com/138 )

1차원 bool 배열로 중복 체크를 해주었던 부분만 제거하면 이 문제의 정답이 됩니다.

▶ 구현

---

#include<iostream>
#include<vector>
using namespace std;
 
void dfs(int N, int M, vector<int>& vt){
    if(vt.size() == M){
        for(int i: vt)
            cout<<i<<" ";
        cout<<"\n";
        return;
    }
 
    for(int n=1; n<=N; n++){
        vt.push_back(n);
        dfs(N,M,vt);
        vt.pop_back();
    }
}
int main(){
    int N,M;
    vector<int> vt;
    cin>>N>>M;
    dfs(N,M,vt);
    return 0;
}

▶ 결과

---