[BOJ] 백준 6603 로또

출처: https://www.acmicpc.net/problem/6603

 Input 

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 34

0

 

 Output 

1 2 3 4 5 6

1 2 3 4 5 7

1 2 3 4 6 7

1 2 3 5 6 7

1 2 4 5 6 7

1 3 4 5 6 7

2 3 4 5 6 7

 

1 2 3 5 8 13

1 2 3 5 8 21

1 2 3 5 8 34

1 2 3 5 13 21

1 2 3 5 13 34

1 2 3 5 21 34

1 2 3 8 13 21

1 2 3 8 13 34

1 2 3 8 21 34

1 2 3 13 21 34

1 2 5 8 13 21

1 2 5 8 13 34

1 2 5 8 21 34

1 2 5 13 21 34

1 2 8 13 21 34

1 3 5 8 13 21

1 3 5 8 13 34

1 3 5 8 21 34

1 3 5 13 21 34

1 3 8 13 21 34

1 5 8 13 21 34

2 3 5 8 13 21

2 3 5 8 13 34

2 3 5 8 21 34

2 3 5 13 21 34

2 3 8 13 21 34

2 5 8 13 21 34

3 5 8 13 21 34

 

K개의 숫자중에서 6개의 숫자를 선택하는 경우로

중복없는 조합을 구현 ← DFS 이용

---

#include <iostream>
#include <cstring>
#include <vector>
#include<algorithm>
using namespace std;
 
int k;
int arr[13];
bool selected[13];
vector<int> vec;
 
void DFS(int idx, int cnt){
    if (cnt == 6){
        sort(vec.begin(), vec.end());
        for (int i = 0; i < vec.size(); i++)
            cout << vec[i] << " ";
        cout << endl;
        return;
    }
 
    for (int i = idx; i < k; i++){
        if (selected[i]) continue;
        
        selected[i] = true;
        vec.push_back(arr[i]);
        
        DFS(i, cnt + 1);
        
        selected[i] = false;
        vec.pop_back();        
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    while(1){
        cin >> k;
        if (k == 0) break;
        
        for (int i = 0; i < k; i++)
            cin >> arr[i];
        
        DFS(0, 0); 
        cout << endl;
    }
}