HackerRank Combinatorics – Building a List

Challenge: Building a List

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464728784

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/building-a-list/problem

Cerinta

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.

Cod sursa

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1;
    cin>>t;
    while(t--){
        int n;
        cin>>n;

        string s;
        cin>>s;
        vector<string> si;
        for(ll i=1;i<(1<<n);i++){
            string rt = "";
            for(ll j=0;j<n;j++){
                if(i&(1<<j)) rt+=s[j];
            }
            si.pb(rt);
        }
        sort(si.begin(), si.end());
        for(ll i=0;i<(1<<n)-1;i++){
            cout<<si[i]<<"\n";
        }
    }
    return 0;
}