6630..md

description	N-Queen Style 백트래킹 - 백트래킹도 자주 연습해야겠다

6630. 로또

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int exp(int i)
{
    int a = 1;
    for (int j=0; j<i; j++)
    {
        a *= 2;
    }
    
    return a;
}

int count(vector<int> v)
{
    int cnt = 0;
    for (int i : v)
    {
        cnt += i;
    }
    
    return cnt;
}

void lotto_logic(vector<int> &answer, vector<int> visited, vector<int> &vec, int n)
{
    if (count(visited) == 6) // 완성? 중복 체크, 출력, return
    {
        int temp = 0; // 중복 check용
        for (int i=0; i<n; i++)
        {
            if (visited[i] == 1) // 방문했다면?
            {
                temp += exp(i); // i==0이라면 2^0==1, 아니라면 2*i를 더하도록 지시 - Bitamsking
            }
        }
        if (find(answer.begin(), answer.end(), temp) == answer.end()) // answer에 없으면?
        {
            for (int i=0; i<n; i++)
            {
                if (visited[i] == 1) // 방문했다면?
                {
                    cout << vec[i] << " ";
                }
            }
            cout << "\n";
            answer.push_back(temp);
            return;
        }
    }
    else // 아직 덜 됐어? 그럼 방문하지 않은 녀석들에 대해 Backtracking!
    {
        for (int i=0; i<n; i++)
        {
            if (visited[i] == 0) // 방문 아직 안했다면 넣고 재귀!
            {
                visited[i] = 1;
                lotto_logic(answer, visited, vec, n);
                visited[i] = 0;
            }
        }
    }
}

void lotto(int n)
{
//    MARK: INDEX에 대한 BackTracking을 진행해야겠고만!
    
    vector<int> vec(n);
    for (int i=0; i<n; i++)
    {
        cin >> vec[i];
    }
    
    vector<int> answer;
    vector<int> visited(n); // 방문 확인
    lotto_logic(answer, visited, vec, n);

    return;
}

int main()
{
    int n;
    cin >> n;
    while (n!=0)
    {
        lotto(n);
        cout << "\n";
        cin >> n;
    }
    return 0;
}