[dfs] orders (알파벳 사전식 정렬)

프로그램 명: orders

제한시간: 1 초

[문제 요약] 알파벳 소문자가 입력으로 주어진다. 이를 사전순으로 정렬하여 출력하는 프로그램. 단 , 같은 것을 포함하는 문자열이고 , 문자수는 200 자를 넘지 않고 출력시 중복을 허락하지 않는다.

출력의 크기는 최대 2 메가바이트를 넘지 않는다.

입력

Input contains a single line with all labels of the requested goods (in random order). Each kind of goods is represented by the starting letter of its label. Only small letters of the English alphabet are used. The number of orders doesn't exceed 200.

출력

Output will contain all possible orderings in which the stores manager may visit his warehouses. Every warehouse is represented by a single small letter of the English alphabet -- the starting letter of the label of the goods. Each ordering of warehouses is written in the output file only once on a separate line and all the lines containing orderings have to be sorted in an alphabetical order (see the example). No output will exceed 2 megabytes.

입출력 예

입력

bbjd

출력

bbdj
bbjd
bdbj
bdjb
bjbd
bjdb
dbbj
dbjb
djbb
jbbd
jbdb
jdbb

출처: CEOI 1999

#include <stdio.h>
#include <string.h>
 
#define MAX 205
 
char arr[MAX];
char in[MAX];
int alpha[26];
int len;
 
void input()
{
    int i;
    scanf("%s", in);
    len = strlen(in);
 
    for(i=0; i<len; i++)
        alpha[in[i] - 'a'] ++;
}
 
void dfs(int depth)
{
    int i;
    if(depth == len)
    {
        printf("%s\n", arr);
        arr[depth] = '\0';
    }
 
    for(i=0; i<26; i++)
    {
        if(alpha[i] > 0 )
        {
            alpha[i]--;
            arr[depth] = 'a' + i;
            dfs(depth+1);
            alpha[i]++;
        }
    }
}
 
int main(void)
{
    input();
    dfs(0);
    return 0;
}