Description
数组中可能包含重复的数字， 求由这些数字组成的不重复字符串， 且字符串中不包含逆序对。
Input
有若干组测试数据，（1～20之间） 每一组测试数据第一行输入一个整数 n (0 ≤ n ≤ 20)， 代表 n 个数字，接下来的一行输入 n 个整数，分别为 x1， x2 … xn (1 ≤ xi ≤ 9)
Output
输出每组数字组成的不重复字符串，字符串通过逗号隔开
Sample
#0
Input
Copy
4 3 1 2 3 8 3 4 5 1 6 1 5 5
Output
Copy
,1,12,123,1233,13,133,2,23,233,3,33 ,1,11,113,1134,11345,113455,1134555,11345556,1134556,113456,11346,1135,11355,113555,1135556,113556,11356,1136,114,1145,11455,114555,1145556,114556,11456,1146,115,1155,11555,115556,11556,1156,116,13,134,1345,13455,134555,1345556,134556,13456,1346,135,1355,13555,135556,13556,1356,136,14,145,1455,14555,145556,14556,1456,146,15,155,1555,15556,1556,156,16,3,34,345,3455,34555,345556,34556,3456,346,35,355,3555,35556,3556,356,36,4,45,455,4555,45556,4556,456,46,5,55,555,5556,556,56,6
Hint
不选择任何数字时，组成空字符串
回溯求组合数然后排序
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
using namespace std;
void DFS(set<string> &ans, vector<int> a, int index, string path)
{//cout << "path=" << path << "OK" << endl;if (index == a.size()){ans.insert(path);return;}//cout << path << " ";DFS(ans, a, index+1, path);DFS(ans, a, index + 1, path + char(a[index] + '0'));}
int main()
{int n;while (cin >> n){vector<int> a;int sd;for (int i = 0; i < n; i++){cin >> sd;a.push_back(sd);}//a.push_back(0);sort(a.begin(), a.end());set<string> s;vector < string>s2;string str="";DFS(s, a, 0, str);for (set<string>::iterator it2 = s.begin(); it2 != s.end(); it2++) {s2.push_back(*it2);}sort(s2.begin(), s2.end());for (vector<string>::iterator it = s2.begin(); it != s2.end(); it++){if (it == s2.begin()) {cout << *it;}else {cout << "," << *it;}}cout << endl;}return 0;
}
