Print all the combinations of a string in lexicographical order | C ++ program to find all combinations of a string in lexicographical order ; function to print string ; Method to found all combination of string it is based in tree ; return if level is equal size of string ; if occurrence of char is 0 then skip the iteration of loop ; decrease the char occurrence by 1 ; store the char in result ; print the string till level ; call the function from level + 1 ; backtracking ; declare the map for store each char with occurrence ; initialize the input array with all unique char ; initialize the count array with occurrence the unique char ; temporary char array for store the result ; store the element of input array ; store the element of count array ; size of map ( no of unique char ) ; size of original string ; call function for print string combination ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void printResult ( char * result , int len ) { for ( int i = 0 ; i <= len ; i ++ ) cout << result [ i ] ; cout << endl ; } void stringCombination ( char result [ ] , char str [ ] , int count [ ] , int level , int size , int length ) { if ( level == size ) return ; for ( int i = 0 ; i < length ; i ++ ) { if ( count [ i ] == 0 ) continue ; count [ i ] -- ; result [ level ] = str [ i ] ; printResult ( result , level ) ; stringCombination ( result , str , count , level + 1 , size , length ) ; count [ i ] ++ ; } } void combination ( string str ) { map < char , int > mp ; for ( int i = 0 ; i < str . size ( ) ; i ++ ) { if ( mp . find ( str [ i ] ) != mp . end ( ) ) mp [ str [ i ] ] = mp [ str [ i ] ] + 1 ; else mp [ str [ i ] ] = 1 ; } char * input = new char [ mp . size ( ) ] ; int * count = new int [ mp . size ( ) ] ; char * result = new char [ str . size ( ) ] ; map < char , int > :: iterator it = mp . begin ( ) ; int i = 0 ; for ( it ; it != mp . end ( ) ; it ++ ) { input [ i ] = it -> first ; count [ i ] = it -> second ; i ++ ; } int length = mp . size ( ) ; int size = str . size ( ) ; stringCombination ( result , input , count , 0 , size , length ) ; } int main ( ) { string str = " ABC " ; combination ( str ) ; return 0 ; }