-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathbuilding-a-list.cpp
More file actions
44 lines (39 loc) · 1.08 KB
/
building-a-list.cpp
File metadata and controls
44 lines (39 loc) · 1.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Author: btjanaka (Bryon Tjanaka)
// Problem: (HackerRank) building-a-list
// Title: Building a List
// Link: https://www.hackerrank.com/challenges/building-a-list/problem
// Idea: Sort the string to ensure we always generate strings in lexicographical
// order. Then generate every subset of characters in the string and add them to
// the results. Use a set for the results to ensure that no strings are
// repeated.
// Difficulty: medium
// Tags: complete-search
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
sort(s.begin(), s.end());
set<string> res;
// Iterate through all strings made from subsets of characters. Each string
// will be organized in lexicographical order since s is sorted above.
for (int i = 1; i < (1 << n); ++i) {
string cur;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
cur.push_back(s[j]);
}
}
res.insert(cur);
}
for (const auto& x : res) {
cout << x << '\n';
}
}
return 0;
}