C语言求字母的全部组合

2014-11-24 09:26:54 · 作者: · 浏览: 0

使用的递归的方法:既然是组合,则顺序不要求顺序了。


主要原理就是从第一个字符开始,分两种情况:1.留下此字符;2.去除此字符。 再对剩下的字符求组合。


然后再第二个字符,分两种情况,再对剩下的字符求组合


结果:


orignate string : abc
b
c
cb
a
ac
ab
abc


结果中有些字符的顺序改变了,如cb ,,按正常顺序可能是bc,,,


这是因为我的这个程序的空间复杂度为O(1)


如果你要求产生的组合与原始字符的顺序一致,,则可以使用mask代替,,标记使用不使用此字符。此时空间复杂度为O(N)


反正时间复杂度都为O(N)