제목

문제 B: [귀속 입문] 조합의 출력 시간 제한: 1 Sec 메모리 제한: 128MB 제출: 1062 해결: 655 [제출] [상태] [토론판] [명제인: 외부 도입] 제목 설명 배열과 조합은 자주 사용하는 수학 방법이다. 그 중에서 조합은 n개의 원소에서 r개의 원소(순서와 r<=n)를 추출하는 것이다. 우리는 n개의 원소를 간단하게 자연수 1, 2,..., n으로 이해할 수 있다.현재 당신은 귀속적인 방법으로 모든 조합을 출력하지 않아도 됩니다.예를 들어 n=5, r=3, 모든 조합은 1 2 3 1 2 4 1 2 5 1 3 4 1 4 5 2 3 2 3 5 2 3 5 2 4 5 5 5 5 입력 한 줄 두 개의 자연수 n, r(1 < n < 21, 1 < = r < = n).
모든 조합을 출력하고, 모든 조합이 한 줄을 차지하며, 그 중의 요소는 작은 것부터 큰 것까지 순서대로 배열하고, 모든 조합도 사전 순서대로 배열한다.

2 참조 코드

귀속 버전

#include 

const int MAXN = 100;
bool hashTable[MAXN] = {false};
int A[MAXN];
int N, R;


void BFS(int index, int r){//r： 
    if(r == R + 1) {
        for (int i = 1; i != R + 1; ++i)
        {
            printf("%d ", A[i]);
            if(i <= R) printf(" ");
        }
        printf("
");
        return;
    }

    for (int i = index; i <= N; ++i)// index～N P[r] 
    {
        if(hashTable[i] == false){
            A[r] = i;// A r i
            hashTable[i] = true;
            BFS(i, r + 1);
            hashTable[i] = false;
        }
    }
}

int main(){
    scanf("%d%d", &N, &R);
    BFS(1, 1);

    return 0;
}

창고 버전

#include 
#include 
#include 

using std::stack;
using std::vector;

vector<int> vec;
stack<int> S;
int N, R;

void BFS(int index){

    S.push(index);// vec 
    vec.push_back(index);// 
    int x;
    bool popFlag = false;// 
    while(!S.empty()){
        if(vec.size() == R){
            for (vector<int>::const_iterator it = vec.begin(); it != vec.end(); ++it)
            {
                if(it != vec.begin()){
                    printf(" ");
                }
                printf("%d", *it);
            }
            printf("
");
            popFlag = true;
        }

        x = S.top();


        if(x == N){// 1～N ， ，
            //  1、2、5 2、5， 2
            //  1、4、5 4、5， 4
            S.pop();
            vec.pop_back();
            popFlag = true;
            continue;
        }

        if(popFlag == true){
            S.pop();
            vec.pop_back();
            popFlag = false;
        }

        if(x < N){
            S.push(x + 1);
            vec.push_back(x + 1);
        }

    }


}

int main(){
    scanf("%d%d", &N, &R);
    BFS(1);

    return 0;
}