首页 > 代码库 > 字符串的组合

字符串的组合

2024-07-16 11:52:32   222人阅读

题目：输入一个字符串，求出其所有的组合。比如字符串abc,其组合为：a、b、c、ab 、ac、 bc 、abc。

思路1：采用递归的思想，针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。

思路2：我们可以把一个长度为n的串看成是一个二进制数，然后约定某位是0就代表不取该位，若是1，则表示取该位，比如abc，对应的某个二进制数为100,这就代表取a,不取bc.只要我们从000，每次加1，到111，对应的串就是abc的所有组合.具体如下所示：
0  000
1  001 --->c
2  010 --->b
3  011 --->bc 
4  100 --->a
5  101 --->ac
6  110 --->ab
7  111 --->abc
另外，可以通过让一个数依次右移0~3位，再和1进行位与操作，就可以得到每一位是0还是1了。

代码：

/*
字符串组合
by Rowandjj
2014/8/8
*/
#include<iostream>
#include<math.h>
using namespace std;
void func(char *pStr)
{
	int len = strlen(pStr);//字符串长度
	int num = pow(2,len);//对应的二进制的上限
	for(int i = 1; i < num; i++)
	{
		for(int j = 0; j < len; j++)
		{
			if((i>>j)&1)//依次右移，并判断该位是否为1
			{
				cout<<pStr[len-j-1];//是1就输出对应位置的值
			}
		}
		cout<<endl;
	}
}
int main()
{
	char str[] = "abc";
	func(str);
	return 0;
}



联系
我们