(C++) - 백준(BOJ) 15666번 : N과 M (12)

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

15666번: N과 M (12)

풀이방법1 : set을 사용한 경우

1.자기 자신도 탐색한다.(check할 필요가 없음)

2.오름차순으로 출력한다.(탐색의 시작을 node라는 변수부터 실행한다.)

3.중복해서 출력이 되면 안된다.(set을 사용한다.)

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int n, m;
int a[8];
int ck[8];
int tmp[8];
set<vector<int>> ans;
//중복 저장을 하지 않는 set이용
void DFS(int level,int node)
{
    if (level == m)
    {
        vector<int> v;
        for (int i = 0; i < m; i++)
            v.push_back(tmp[i]);
        //set에 무조건 때려박는다
        ans.insert(v);
        v.clear();
        return;
    }
    for (int i = node; i < n; i++)
    {    
        tmp[level] = a[i];
        DFS(level + 1, i);
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);//정렬
    DFS(0,0);
 
    for (auto a : ans)
    {
        for (int i = 0; i < a.size(); i++)
        {
            cout << a[i] << ' ';
        }
        cout << '\n';
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
int n, m;
int a[10];
int ck[10];
int b[10];
 
void foo(int depth,int index){
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << b[i] << ' ';
        }
        cout << '\n';
        return;
    }
 
    for (int i = index; i < n; i++) {
        b[depth] = a[i];
        foo(depth + 1, i);
        //같은 것이 나오는 동안 index 스킵
        while (a[i] == a[i + 1]) {
            i++;
        }
    }
}
int main() {
    fastio;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    foo(0,0);
}