Hackerrank - Building a List

Chan has decided to make a list of all possible combinations of letters of a given string S. If there are two strings with the same set of characters, print the lexicographically smallest arrangement of the two strings.

abc acb cab bac bca

all the above strings' lexicographically smallest string is abc.

Each character in the string S is unique. Your task is to print the entire list of Chan's in lexicographic order.

for string abc, the list in lexicographic order is given below

a ab abc ac b bc c

Input Format 
The first line contains the number of test cases T. T testcases follow. 
Each testcase has 2 lines. The first line is an integer N ( the length of the string). 
The second line contains the string S.

Output Format 
For each testcase, print the entire list of combinations of string S, with each combination of letters in a newline.

Constraints 
0< T< 50 
1< N< 16 
string S contains only small alphabets(a-z)

Sample Input

2
2
ab
3
xyz

Sample Output

a
ab
b
x
xy
xyz
xz
y
yz
z

Explanation 
In the first case we have ab, the possibilities are a, ab and b. Similarly, all combination of characters of xyz.

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos (0.0);
8.  
9. int _Int(){int x; scanf("%d", &x); return x;}
10. LL _LLi(){LL x; scanf("%lld", &x); return x;}
11. void pruts(){puts("-1");exit(EXIT_SUCCESS);}
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. string s, Ans[ (1<<16)+2 ];
31.  
32. void Love(){
33.     int t = _Int();
34.     while( t-- ){
35.         int n = _Int();
36.         cin >> s;
37.         int k = 0;
38.         for( int i = 1; i < ( 1 << n ); i++ ){
39.             int ind = 0;
40.             int v = i;
41.             string temp;
42.             while( v ){
43.                 if( v&1 )temp.pb(s[ind]);
44.                 ind++;
45.                 v >>= 1;
46.             }
47.             if( temp.size() )Ans[k++] = temp;
48.             temp.clear();
49.         }
50.         sort(Ans, Ans+k);
51.         for( int i = 0; i < k; i++ )cout << Ans[i] << endl;
52.         for( int i = 0; i < k; i++ )Ans[i].clear();
53.     }
54. }
55.  
56. int main(){
57.     #ifndef ONLINE_JUDGE
58. //        freopen("in.txt", "r", stdin);
59. //        freopen("n.txt", "w", stdout);
60.     #endif
61.     Love();
62.     return 0;
63. }