这道题，如果用 C++，那么可以这样写去重：
string str;
cin >> str;
sort(str.begin(), str.end());
str.erase(unique(str.begin(), str.end()), str.end());
详见 C++ Primer (5th Ed.) 中文版 P343 或英文版 P384 关于 unique 等函数用法的讲解。
然后是排序输出的问题。可以简单地想到一个朴素算法：枚举去重后的字符串 str 中的每一个字符，分别有两种情况：
- 加
- 不加
我以 "abc" 来解释一下。对第一个字符 'a'，有要和不要两种选择，那么可以组出：
{"a", ""};
然后，对第二个字符，有要和不要两种选择，那么可以组出：
{"ab", "b", "a", ""};
^^^^^^^^^ ^^^^^^^
选 'b' 不选 'b'
第三个同理。
可以发现，每次「不选」的情况下得到的结果就是上一步的内容，那么可以写出这样的等价的代码：
vector<string> strs({""});
for (uint32_t i = 0; i < str.size(); ++i) {
for (uint32_t j = 0, sz = strs.size(); j < sz; ++j) {
strs.push_back(strs[j] + str[i]);
}
}
思考：如果一开始没有在
strs里加入一个空字符串会怎样？
由于要按字典序输出，所以再排序一下就好了。从下标 1 开始输出，因为打头的元素是我们放置的哨兵空字符。
完整代码：
int main() {
using namespace std;
uint32_t t; cin >> t;
for (uint32_t query = 0; query < t; ++query) {
printf("case #%u:\n", query);
string str; cin >> str;
sort(str.begin(), str.end());
str.erase(unique(str.begin(), str.end()), str.end());
vector<string> strs({""});
for (uint32_t i = 0; i < str.size(); ++i) {
for (uint32_t j = 0, sz = strs.size(); j < sz; ++j) {
strs.push_back(strs[j] + str[i]);
}
}
sort(strs.begin(), strs.end());
for (uint32_t i = 1; i < strs.size(); ++i) {
printf("%s\n", strs[i].data());
}
}
}
不过按我一开始的想法不是这么做的。
观察输出的要求，可以看出就是在对 (0..str.size()) 的每个字符，在前面的选择的基础上，依次做这三种选择：
- 加入当前位置的字符，并在此停止（把这个字符串放入答案数组）。
- 加入当前位置的字符，并继续添加。
- 不加入当前位置的字符，并继续添加。
代码：
std::string str;
std::vector<std::string> strs;
void arrange(uint32_t step, std::string const &crnt_str) {
if (step != (uint32_t)str.size()) {
strs.push_back(crnt_str + str[step]);
arrange(step + 1, crnt_str + str[step]);
arrange(step + 1, crnt_str);
}
}
int main() {
using namespace std;
uint32_t t; cin >> t;
for (uint32_t query = 0; query < t; ++query) {
printf("case #%u:\n", query);
cin >> str;
sort(str.begin(), str.end());
str.erase(unique(str.begin(), str.end()), str.end());
strs.clear();
arrange(0, string(""));
for (auto const &s : strs) {
printf("%s\n", s.data());
}
}
}
nice