Iterative approach to print all combinations of an Array | C ++ implementation of the approach ; Data array for combination ; Number of elements in the combination ; The boolean array ; Starting index of the 1 st tract of trues ; Ending index of the 1 st tract of trues ; Constructor ; Set the 1 st r Booleans to true , initialize Start and End ; Generate the very first combination ; Update the starting ending indices of trues in the boolean array ; Function that returns true if another combination can still be generated ; Function to generate the next combination ; Only one true in the tract ; Move the End and reset the End ; Set all the values to false starting from index Start and ending at index End in the boolean array ; Set the beginning elements to true ; Reset the End ; Function to print the combination generated previouslt ; If current index is set to true in the boolean array then element at current index in the original array is part of the combination generated previously ; Driver code
#include <iostream> NEW_LINE using namespace std ; class Combination { private : int * Indices ; int N ; int R ; bool * Flags ; int Start ; int End ; public : Combination ( int * arr , int n , int r ) { this -> Indices = arr ; this -> N = n ; this -> R = r ; this -> Flags = nullptr ; } ~ Combination ( ) { if ( this -> Flags != nullptr ) { delete [ ] this -> Flags ; } } void GetFirst ( ) { this -> Flags = new bool [ N ] ; for ( int i = 0 ; i < this -> N ; ++ i ) { if ( i < this -> R ) { Flags [ i ] = true ; } else { Flags [ i ] = false ; } } this -> Start = 0 ; this -> End = this -> R - 1 ; this -> Output ( ) ; } bool HasNext ( ) { return End < ( this -> N - 1 ) ; } void Next ( ) { if ( this -> Start == this -> End ) { this -> Flags [ this -> End ] = false ; this -> Flags [ this -> End + 1 ] = true ; this -> Start += 1 ; this -> End += 1 ; while ( this -> End + 1 < this -> N && this -> Flags [ this -> End + 1 ] ) { ++ this -> End ; } } else { if ( this -> Start == 0 ) { Flags [ this -> End ] = false ; Flags [ this -> End + 1 ] = true ; this -> End -= 1 ; } else { Flags [ this -> End + 1 ] = true ; for ( int i = this -> Start ; i <= this -> End ; ++ i ) { Flags [ i ] = false ; } for ( int i = 0 ; i < this -> End - this -> Start ; ++ i ) { Flags [ i ] = true ; } this -> End = this -> End - this -> Start - 1 ; this -> Start = 0 ; } } this -> Output ( ) ; } private : void Output ( ) { for ( int i = 0 , count = 0 ; i < this -> N && count < this -> R ; ++ i ) { if ( Flags [ i ] ) { cout << Indices [ i ] << " ▁ " ; ++ count ; } } cout << endl ; } } ; int main ( ) { int arr [ ] = { 0 , 1 , 2 , 3 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int r = 3 ; Combination com ( arr , n , r ) ; com . GetFirst ( ) ; while ( com . HasNext ( ) ) { com . Next ( ) ; } return 0 ; }