2014百度笔试题

算法题：给出一个数据A=[a_0, a_1, a-2, ... a_n](其中n可变)，打印出该数值元素的所有组合。

注：此题要求输出的是所有的组合，并非所有排列。

思路：数组中的每一个数对应一个标志位，将标志位数组中的每个元素看成是一个只能为0或1的元素，将这个标志位数组从1循环到2^n - 1，每次迭代加1，迭代过程中输出此时标志位为1的对应元素。

代码如下：

#include <iostream> #include <algorithm> #include <vector> #include <queue>#include <stack>#include <string> #include <string.h> #include <fstream> #include <map> #include <iomanip> #include <cstdio> #include <cstdlib>#include <cmath>using namespace std; const int MAX = 0x7FFFFFFF; const int MIN = 0x80000000; void print(string str, int n){int *flag = new int[n + 1];for(int i = 0; i < n + 1; i++)flag[i] = 0;flag[0] = 1;double count = 0;count = pow(2.0,(double)n) - 1;for(int num = 1; num <= count; num++){for(int i = 0; i < n; i++)if(flag[i] == 1)cout << str[i];cout << endl;int cur = 1;for(int i = 0; i < n; i++){if(flag[i] + cur  == 0)break;if(flag[i] + cur == 1){flag[i] = 1;break;}if(flag[i] + cur == 2){flag[i] = 0;cur = 1;}}}delete[] flag;}int main(){string str;//输入为字符串while(cin >> str){print(str, str.length());}return 0;}