POJ 1731 Orders 解题报告

一、问题描述

大意是求出一个字符集的全排列，不能有相同的，并按字典顺序输出所有排列

Sample Input

bbjd

Sample Output

bbdj

bbjd

bdbj

bdjb

bjbd

bjdb

dbbj

dbjb

djbb

jbbd

jbdb

jdbb

 

二、解题思路

利用递归回溯求解，先将字符从小到大进行排序。然后使用回溯法。因为不能有相同的排列，故在回溯时如果下一个字符和上一个字符相同，则跳过该字符直到一个不同的字符。

三、代码

 

#include<iostream>
using namespace std;
char s[205];
char res[205];
bool b[205];
int N;
int cmp(const void * a,const void * b)
{
    return *(char * )a-*(char *)b;
}
void backtrace(int n)
{
    if(n==N)
    {
        printf("%s\n",res);
        return ;
    }
    int i;
    for(i=0;i<N;++i)
    {
        if(b[i]==false)
        {
            res[n]=s[i];
            b[i]=true;
            backtrace(n+1);
            b[i]=false;
            while(i<(N-1) && s[i]==s[i+1])//跳过相同的字符
                i++;
        }    
    }
}
int main()
{
    scanf("%s",&s);
    N=strlen(s);
    res[N]='\0';
    qsort(s,N,sizeof(char),cmp);
    memset(b,0,sizeof(b));
    backtrace(0);
    return 0;
}