给定字符串输出该字符串的所有可能排列

给定一个无重复字符串字符串，程序输出该字符串的所有排列。

回溯算法。

codepad.org已验证

 

Dec 21th 2012 update

根据socay2 提醒 增加30 31行free释放内存，更改标题

 

Jan 2rd 2013 update

1.代码中其实无需使用malloc,这样就减少了free的负担，直接在栈上开辟空间然后memcopy即可。

2.对于含重复字符的解法，查找到了基于交换元素的回溯解决方案，具体分析和代码参见

http://blog.chinaunix.net/uid-26456800-id-3457862.html

3.根据2的解法，对本文给出的基于选择的回溯法进行了改进，以处理重复字符串，同时精简了代码。代码见第二部分。

//无重复字符

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void append(char *src, char app){
    if(src == NULL) return;
    char* start = src;
    while(*start)start++;
    *start = app;
    start++;
    *start = '\0';
}
void allCombine(const char* word, int len, char* set){

    if(word == NULL) return;
    if(strlen(set) == len){
        printf("%s \n", set);
        return;
    }
    int i = 0;
    for(;i<len;i++){
        if(word[i]){
            char* afterselect = (char*)malloc(sizeof(char)*(len+1));
            memcpy(afterselect,word,len);
            afterselect[i]= '\0';
            char *newset = (char*)malloc(sizeof(char)*(len+1));
            memcpy(newset, set,len);
            append(newset, word[i]);
            allCombine(afterselect,len,newset);
            free(newset);
            free(afterselect);
        }
    }

}

int main(){

    char *word = "abcde";
        char set[strlen(word)+1];
        set[0] = '\0';
    allCombine(word, strlen(word),set);
    return 0;
}

//有重复字符

#include <memory.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void allCombine(char* word, int len, char* set){
    if(word == NULL) return;
    if(strlen(set) == len){
        printf("%s \n", set);
        return;
    }
    char record[256] = {0};
    int i = 0;
    for(;i<len;i++){
        if(word[i] && record[word[i]]!= 1 ){
            record[word[i]] = 1;
            int tlen = strlen(set);
            set[strlen(set)] = word[i];
                        set[tlen+1] = '\0';
            char tmp = word[i];
            word[i] = '\0';
            allCombine(word,len,set);
            word[i] = tmp;
            set[tlen] = '\0';
        }
    }
}

int main(){
    char word[] = "aab";
    char set[strlen(word)+1];
        set[0] = '\0';
    allCombine(word, strlen(word),set);
    printf("%s \n", set);
    return 0;

}