C語言求字母的全部組合

使用的遞歸的方法：既然是組合，則順序不要求順序了。

主要原理就是從第一個字符開始，分兩種情況：1.留下此字符；2.去除此字符。 再對剩下的字符求組合。

然後再第二個字符，分兩種情況，再對剩下的字符求組合

1. #include <stdlib.h>
2. #include <stdio.h>
3. #include <string.h>
5. template <typename T>
6. inlinevoid swap(T &a , T &b)
7. {
8. T tmp;
9. tmp = a;
10. a = b;
11. b = tmp;
12. }
14. void doPrintAllCombination(char *str , int begin , int end)
15. {
16. if(begin == end) {
17. char tmp;
18. if(end != 0) { //i要此字符時
19. tmp = str[end];
20. str[end] = '\0';
21. printf("%s\n",str);
22. str[end] = tmp;
23. }
25. tmp = str[end+1]; //不要此字符
26. str[end+1] = '\0';
27. printf("%s\n" , str);
28. str[end+1] = tmp;
29. return;
30. }
31. //第二種情況，去除此字符
32. swap(str[begin],str[end]);
33. doPrintAllCombination(str , begin , end-1);
34. swap(str[begin] , str[end]);
35. //第一種情況，留下此字符
36. doPrintAllCombination(str , begin+1 , end);
37. }
38. void printAllCombination(char *str)
39. {
40. doPrintAllCombination(str , 0 , strlen(str)-1);
41. }
43. int main(int argc , char *argv[])
44. {
45. if(argc != 2) {
46. printf("usage: %s <string>\n" , argv[0]);
47. return -1;
48. }
50. char *str = (char*)malloc(strlen(argv[1]) + 1);
51. strcpy(str , argv[1]);
52. printf("orignate string : %s\n" , str);
53. printAllCombination(str);
54. free(str);
55. return 0;
56. }

結果：

orignate string : abc
b
c
cb
a
ac
ab
abc

結果中有些字符的順序改變了，如cb ,,按正常順序可能是bc,,,

這是因為我的這個程序的空間復雜度為O(1)

如果你要求產生的組合與原始字符的順序一致，，則可以使用mask代替，，標記使用不使用此字符。此時空間復雜度為O(N)

反正時間復雜度都為O(N)