[BOJ] 백준 15656. N과 M (7)

▶문제설명

[BOJ] 백준 15656. N과 M (7)

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

▶ 설계

---

[문제]

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

N개의 자연수는 모두 다른 수이다.

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

 중복되는 수열을 여러 번 출력하면 안된다.

N과 M (5) 문제와 거의 같은 문제입니다.

진하게 표시된 '같은 수를 여러 번 골라도 된다'는 조건이 추가되었습니다.

[N과 M (5) 풀이 바로가기]

 : https://it-earth.tistory.com/143

N과 M (5) 문제에서는 나왔던 수를 체크하면서 수가 중복되지 않도록 해주었는데

그 부분만 제외해주면 이 문제의 정답이 됩니다.

▶ 구현

---

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
void dfs(const vector<int>& numbers, int m, vector<int>& vt){
    if(vt.size() == m){
        for(int n : vt)
            cout<<n<<" ";
        cout<<"\n";
        return;
    }
 
    for(int i=0; i<numbers.size(); i++){
        vt.push_back(numbers[i]);
        dfs(numbers,m,vt);
        vt.pop_back();
    }
}
 
int main(){
    int n,m;
    vector<int> numbers, vt;
    cin>>n>>m;
    for(int i=0,k; i<n; i++){
        cin>>k;
        numbers.push_back(k);
    }
    sort(numbers.begin(), numbers.end());
    dfs(numbers,m,vt);
    return 0;
}

▶ 결과

---