[백트랙킹]로또

백준6603

주어진 수의 집합으로 가능한 모든 6자리 조합을 출력하면 된다. 문제를 해결하기 위해 백트랙킹을 사용할 때는, 두 가지 방법이 있다.

첫 번째는 문제에서 중복되는 조합 (i,j) ↔ (j,i) 를 허용하는지의 여부이다.

만약 문제에서 중복되는 조합을 허용한다면,

void func(int n){
	if(n==@){
		cout 
		return
	}
	for(int i=0;i<$;i++){
		func(n+1)
	}
}

의 형태를 따르면 된다. 기저 조건이 아닐 때 동작하는 반복문이 0에서 시작하는 것을 잘 확인해보면 된다.

만약 문제에서 중복되는 조합을 허용하지 않는다면, 즉 현재 문제처럼 1 2 3 4 5 6 7 과 7 6 5 4 3 2 1 이 같은 조합으로 취급되거나 오름차순, 내림차순 등의 출력을 요구한다면,

void func(int n,int start){
	if(n==@){
		cout 
		return
	}
	for(int i=start;i<$;i++){
		func(n+1,i+1)
	}
}

의 형태를 따르면 된다. 기저 조건이 아닐 때 동작하는 반복문이 직전에 호출한 인덱스부터 시작하는 것을 볼 수 있다.

첫 번째 방법을 사용하면 1 2 3 과 3 2 1 은 다른 조합으로 취급된다.

두 번째 방법을 사용하면 1 2 3 과 3 2 1 은 같은 조합으로 취급된다.

상황에 따라 맞는 방법을 택하면 된다.

현재 문제에서는 번호를 고르는 경우의 수를 요구하고 있기 때문에 두 번째 방법을 사용하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int K;
vector<int> num;
int arr[6];
bool isUsed[50];

void init(){
    fill(isUsed,isUsed+50,false);
    num.clear();
}

void btk(int n, int start){
    if(n==6){
        for(int i=0;i<6;i++){
            cout << arr[i] << " ";  
        }
        cout << "\n";
        return;
    }
    for(int i=start;i<K;i++){
        if(!isUsed[num[i]]){
            arr[n] = num[i];
            isUsed[num[i]] = true;
            btk(n+1,i+1);
            isUsed[num[i]] = false;
        }
    }
}

int main(){
    
    while(1){
        cin >> K;
        if(K==0){
            return 0;
        }
        else{
            for(int i=0;i<K;i++){
                int temp; 
                cin >> temp;
                num.push_back(temp);
            }
        }
        btk(0,0);
        cout << endl;
        init();
        
    }
}