Given an array arr[] of size N, the task is to generate and print all possible combinations of R elements in array. Examples:
Input: arr[] = {0, 1, 2, 3}, R = 3 Output: 0 1 2 0 1 3 0 2 3 1 2 3 Input: arr[] = {1, 3, 4, 5, 6, 7}, R = 5 Output: 1 3 4 5 6 1 3 4 5 7 1 3 4 6 7 1 3 5 6 7 1 4 5 6 7 3 4 5 6 7
Approach: Recursive methods are discussed here. In this post, an iterative method to output all combinations for a given array will be discussed. The iterative method acts as a state machine. When the machine is called, it outputs a combination and move to the next one. For a combination of r elements from an array of size n, a given element may be included or excluded from the combination. Let’s have a Boolean array of size n to label whether the corresponding element in data array is included. If the ith element in the data array is included, then the ith element in the boolean array is true or false otherwise. Then, r booleans in the boolean array will be labelled as true. We can initialize the boolean array to have r trues from index 0 to index r – 1. During the iteration, we scan the boolean array from left to right and find the first element which is true and whose previous one is false and the first element which is true and whose next one is false. Then, we have the first continuous tract of trues in the Boolean array. Assume there are m trues in this tract, starting from index Start and ending at index End. The next iteration would be
- Set index End + 1 of the boolean array to true.
- Set index Start to index End – 1 of the boolean array to false.
- Set index 0 to index k – 2 to true.
For example, If the current boolean array is {0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0}, then k = 4, Start = 2, and End = 5. The next Boolean array would be {1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0}. In case Start == End where there is only one true in the tract, we simply set index End to false and index End + 1 to true. We also need to record the current Start and End and update Start and End during each iteration. When the last r booleans are set to true, we cannot move to the next combination and we stop. The following image illustrates how the boolean array changes from one iteration to another. To output the combination, we just scan the boolean array. If its ith index is true, we print out the ith element of the data array. Below is the implementation of the above approach:Â
C++
// C++ implementation of the approach #include <iostream> using namespace std; Â
class Combination { private :     // Data array for combination     int * Indices; Â
    // Length of the data array     int N; Â
    // Number of elements in the combination     int R; Â
    // The boolean array     bool * Flags; Â
    // Starting index of the 1st tract of trues     int Start; Â
    // Ending index of the 1st tract of trues     int End; Â
public :     // Constructor     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;         }     } Â
    // Set the 1st r Booleans to true,     // initialize Start and End     void GetFirst()     {         this ->Flags = new bool [N]; Â
        // Generate the very first combination         for ( int i = 0; i < this ->N; ++i) {             if (i < this ->R) {                 Flags[i] = true ;             }             else {                 Flags[i] = false ;             }         } Â
        // Update the starting ending indices         // of trues in the boolean array         this ->Start = 0;         this ->End = this ->R - 1;         this ->Output();     } Â
    // Function that returns true if another     // combination can still be generated     bool HasNext()     {         return End < ( this ->N - 1);     } Â
    // Function to generate the next combination     void Next()     { Â
        // Only one true in the tract         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 { Â
            // Move the End and reset the End             if ( this ->Start == 0) {                 Flags[ this ->End] = false ;                 Flags[ this ->End + 1] = true ;                 this ->End -= 1;             }             else {                 Flags[ this ->End + 1] = true ; Â
                // Set all the values to false starting from                 // index Start and ending at index End                 // in the boolean array                 for ( int i = this ->Start; i <= this ->End; ++i) {                     Flags[i] = false ;                 } Â
                // Set the beginning elements to true                 for ( int i = 0; i < this ->End - this ->Start; ++i) {                     Flags[i] = true ;                 } Â
                // Reset the End                 this ->End = this ->End - this ->Start - 1;                 this ->Start = 0;             }         }         this ->Output();     } Â
private :     // Function to print the combination generated previouslt     void Output()     {         for ( int i = 0, count = 0; i < this ->N                                    && count < this ->R;              ++i) { Â
            // 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             if (Flags[i]) {                 cout << Indices[i] << " " ;                 ++count;             }         }         cout << endl;     } }; Â
// Driver code 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; } |
Java
// Java implementation of the approach class Combination { Â
    // Data array for combination     private int [] Indices; Â
    // Number of elements in the combination     private int R; Â
    // The boolean array     private boolean [] Flags; Â
    // Starting index of the 1st tract of trues     private int Start; Â
    // Ending index of the 1st tract of trues     private int End; Â
    // Constructor     public Combination( int [] arr, int r)     {         this .Indices = arr;         this .R = r;     } Â
    // Set the 1st r Booleans to true,     // initialize Start and End     public void GetFirst()     {         Flags = new boolean [ this .Indices.length]; Â
        // Generate the very first combination         for ( int i = 0 ; i < this .R; ++i)         {             Flags[i] = true ;         } Â
        // Update the starting ending indices         // of trues in the boolean array         this .Start = 0 ;         this .End = this .R - 1 ;         this .Output();     } Â
    // Function that returns true if another     // combination can still be generated     public boolean HasNext()     {         return End < ( this .Indices.length - 1 );     } Â
    // Function to generate the next combination     public void Next()     { Â
        // Only one true in the tract         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 .Indices.length                 && this .Flags[ this .End + 1 ])             {                 ++ this .End;             }         }         else         { Â
            // Move the End and reset the End             if ( this .Start == 0 )             {                 Flags[ this .End] = false ;                 Flags[ this .End + 1 ] = true ;                 this .End -= 1 ;             }             else             {                 Flags[ this .End + 1 ] = true ; Â
                // Set all the values to false starting from                 // index Start and ending at index End                 // in the boolean array                 for ( int i = this .Start; i <= this .End; ++i)                 {                     Flags[i] = false ;                 } Â
                // Set the beginning elements to true                 for ( int i = 0 ; i < this .End - this .Start; ++i)                 {                     Flags[i] = true ;                 } Â
                // Reset the End                 this .End = this .End - this .Start - 1 ;                 this .Start = 0 ;             }         }         this .Output();     } Â
    // Function to print the combination generated previouslt     private void Output()     {         for ( int i = 0 , count = 0 ; i < Indices.length                                 && count < this .R; ++i)         { Â
            // 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             if (Flags[i])             {                 System.out.print(Indices[i]);                 System.out.print( " " );                 ++count;             }         }         System.out.println();     } } Â
// Driver code class GFG { Â Â Â Â public static void main(String[] args) Â Â Â Â { Â Â Â Â Â Â Â Â int [] arr = { 0 , 1 , 2 , 3 }; Â Â Â Â Â Â Â Â int r = 3 ; Â Â Â Â Â Â Â Â Combination com = new Combination(arr, r); Â Â Â Â Â Â Â Â com.GetFirst(); Â Â Â Â Â Â Â Â while (com.HasNext()) Â Â Â Â Â Â Â Â { Â Â Â Â Â Â Â Â Â Â Â Â com.Next(); Â Â Â Â Â Â Â Â } Â Â Â Â } } Â
// This code is contributed by Rajput-Ji |
Python3
# Python 3 implementation of the approach class Combination :     # Data array for combination     Indices = None          # Number of elements in the combination     R = 0          # The boolean array     Flags = None          # Starting index of the 1st tract of trues     Start = 0          # Ending index of the 1st tract of trues     End = 0          # Constructor     def __init__( self , arr, r) :         self .Indices = arr         self .R = r              # Set the 1st r Booleans to true,     # initialize Start and End     def GetFirst( self ) :         self .Flags = [ False ] * ( len ( self .Indices))                  # Generate the very first combination         i = 0         while (i < self .R) :             self .Flags[i] = True             i + = 1                      # Update the starting ending indices         # of trues in the boolean array         self .Start = 0         self .End = self .R - 1         self .Output()              # Function that returns true if another     # combination can still be generated     def  HasNext( self ) :         return self .End < ( len ( self .Indices) - 1 )            # Function to generate the next combination     def Next ( self ) :                # Only one true in the tract         if ( self .Start = = self .End) :             self .Flags[ self .End] = False             self .Flags[ self .End + 1 ] = True             self .Start + = 1             self .End + = 1             while ( self .End + 1 < len ( self .Indices) and self .Flags[ self .End + 1 ]) :                 self .End + = 1         else :                        # Move the End and reset the End             if ( self .Start = = 0 ) :                 self .Flags[ self .End] = False                 self .Flags[ self .End + 1 ] = True                 self .End - = 1             else :                 self .Flags[ self .End + 1 ] = True                                  # Set all the values to false starting from                 # index Start and ending at index End                 # in the boolean array                 i = self .Start                 while (i < = self .End) :                     self .Flags[i] = False                     i + = 1                                      # Set the beginning elements to true                 i = 0                 while (i < self .End - self .Start) :                     self .Flags[i] = True                     i + = 1                                      # Reset the End                 self .End = self .End - self .Start - 1                 self .Start = 0         self .Output()              # Function to print the combination generated previouslt     def Output( self ) :         i = 0         count = 0         while (i < len ( self .Indices) and count < self .R) :                        # 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             if ( self .Flags[i]) :                 print ( self .Indices[i], end = "")                 print ( " " , end = "")                 count + = 1             i + = 1         print ()          # Driver code class GFG :     @staticmethod     def main( args) :         arr = [ 0 , 1 , 2 , 3 ]         r = 3         com = Combination(arr, r)         com.GetFirst()         while (com.HasNext()) :             com. Next ()      if __name__ = = "__main__" :     GFG.main([])          # This code is contributed by aadityaburujwale. |
C#
// C# implementation of the approach using System; namespace IterativeCombination { class Combination { Â
    // Data array for combination     private int [] Indices; Â
    // Number of elements in the combination     private int R; Â
    // The boolean array     private bool [] Flags; Â
    // Starting index of the 1st tract of trues     private int Start; Â
    // Ending index of the 1st tract of trues     private int End; Â
    // Constructor     public Combination( int [] arr, int r)     {         this .Indices = arr;         this .R = r;     } Â
    // Set the 1st r Booleans to true,     // initialize Start and End     public void GetFirst()     {         Flags = new bool [ this .Indices.Length]; Â
        // Generate the very first combination         for ( int i = 0; i < this .R; ++i) {             Flags[i] = true ;         } Â
        // Update the starting ending indices         // of trues in the boolean array         this .Start = 0;         this .End = this .R - 1;         this .Output();     } Â
    // Function that returns true if another     // combination can still be generated     public bool HasNext()     {         return End < ( this .Indices.Length - 1);     } Â
    // Function to generate the next combination     public void Next()     { Â
        // Only one true in the tract         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 .Indices.Length                    && this .Flags[ this .End + 1]) {                 ++ this .End;             }         }         else { Â
            // Move the End and reset the End             if ( this .Start == 0) {                 Flags[ this .End] = false ;                 Flags[ this .End + 1] = true ;                 this .End -= 1;             }             else {                 Flags[ this .End + 1] = true ; Â
                // Set all the values to false starting from                 // index Start and ending at index End                 // in the boolean array                 for ( int i = this .Start; i <= this .End; ++i) {                     Flags[i] = false ;                 } Â
                // Set the beginning elements to true                 for ( int i = 0; i < this .End - this .Start; ++i) {                     Flags[i] = true ;                 } Â
                // Reset the End                 this .End = this .End - this .Start - 1;                 this .Start = 0;             }         }         this .Output();     } Â
    // Function to print the combination generated previouslt     private void Output()     {         for ( int i = 0, count = 0; i < Indices.Length                                    && count < this .R;              ++i) { Â
            // 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             if (Flags[i]) {                 Console.Write(Indices[i]);                 Console.Write( " " );                 ++count;             }         }         Console.WriteLine();     } } Â
// Driver code class AppDriver { Â Â Â Â static void Main() Â Â Â Â { Â Â Â Â Â Â Â Â int [] arr = { 0, 1, 2, 3 }; Â Â Â Â Â Â Â Â int r = 3; Â Â Â Â Â Â Â Â Combination com = new Combination(arr, r); Â Â Â Â Â Â Â Â com.GetFirst(); Â Â Â Â Â Â Â Â while (com.HasNext()) { Â Â Â Â Â Â Â Â Â Â Â Â com.Next(); Â Â Â Â Â Â Â Â } Â Â Â Â } } } |
Javascript
//Javascript code for the above approach class Combination { // Data array for combination Indices = null ; Â
// Number of elements in the combination R = 0; Â
// The boolean array Flags = null ; Â
// Starting index of the 1st tract of trues Start = 0; Â
// Ending index of the 1st tract of trues End = 0; Â
// Constructor constructor(arr, r) { Â Â Â Â this .Indices = arr; Â Â Â Â this .R = r; } Â
// Set the 1st r Booleans to true, // initialize Start and End GetFirst() {     this .Flags = Array( this .Indices.length).fill( false );          // Generate the very first combination     let i = 0;     while (i < this .R) {         this .Flags[i] = true ;         i += 1;     }          // Update the starting ending indices     // of trues in the boolean array     this .Start = 0;     this .End = this .R - 1;     this .Output(); } Â
// Function that returns true if another // combination can still be generated HasNext() { Â Â Â Â return this .End < ( this .Indices.length - 1); } Â
// Function to generate the next combination Next() {     // Only one true in the tract     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 .Indices.length && this .Flags[ this .End + 1]) {             this .End += 1;         }     } else {         // Move the End and reset the End         if ( this .Start === 0) {             this .Flags[ this .End] = false ;             this .Flags[ this .End + 1] = true ;             this .End -= 1;         } else {             this .Flags[ this .End + 1] = true ;                          // Set all the values to false starting from             // index Start and ending at index End             // in the boolean array             let i = this .Start;             while (i <= this .End) {                 this .Flags[i] = false ;                 i += 1;             }                          // Set the beginning elements to true             i = 0;             while (i < this .End - this .Start) {                 this .Flags[i] = true ;                 i += 1;             }                          // Reset the End             this .End = this .End - this .Start - 1;             this .Start = 0;         }         this .Output();     } } Â
// Function to print the combination generated previouslt Output() {     let i = 0;     let count = 0;     while (i < this .Indices.length && count < this .R) {         // 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 if ( this .Flags[i]) { document.write( this .Indices[i], " " ); count += 1; } i += 1; } document.write( "<br>" ); } } Â
// Driver code class GFG { static main() { let arr = [0, 1, 2, 3]; let r = 3; let com = new Combination(arr, r); com.GetFirst(); while (com.HasNext()) { com.Next(); } } } Â
if (require.main === module) { GFG.main(); } |
Javascript
//JS code for the above approach class Combination { // Data array for combination Indices = null ; Â
// Number of elements in the combination R = 0; Â
// The boolean array Flags = null ; Â
// Starting index of the 1st tract of trues Start = 0; Â
// Ending index of the 1st tract of trues End = 0; Â
// Constructor constructor(arr, r) { Â Â Â Â this .Indices = arr; Â Â Â Â this .R = r; } Â
// Set the 1st r Booleans to true, // initialize Start and End GetFirst() {     this .Flags = Array( this .Indices.length).fill( false );          // Generate the very first combination     for (let i = 0; i < this .R; i++) {         this .Flags[i] = true ;     }          // Update the starting ending indices     // of trues in the boolean array     this .Start = 0;     this .End = this .R - 1;     this .Output(); } Â
// Function that returns true if another // combination can still be generated HasNext() { Â Â Â Â return this .End < ( this .Indices.length - 1); } Â
// Function to generate the next combination Next() { Â
    // Only one true in the tract     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 .Indices.length && this .Flags[ this .End + 1]) {             this .End += 1; } } else { Â
// Move the End and reset the End if ( this .Start === 0) { this .Flags[ this .End] = false ; this .Flags[ this .End + 1] = true ; this .End -= 1; } else { this .Flags[ this .End + 1] = true ; Â
            // Set all the values to false starting from             // index Start and ending at index End             // in the boolean array             for (let i = this .Start; i <= this .End; i++) {                 this .Flags[i] = false ;             }                          // Set the beginning elements to true             for (let i = 0; i < this .End - this .Start; i++) {                 this .Flags[i] = true ;             }                          // Reset the End             this .End = this .End - this .Start - 1;             this .Start = 0;         }     }     this .Output(); } Â
// Function to print the combination generated previously Output() {     for (let i = 0, count = 0; i < this .Indices.length && count < this .R; i++)     {              // 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         if ( this .Flags[i]) {             console.log( this .Indices[i], " " );             count += 1;         }     }     console.log( "<br>" ); } } Â
// Driver code class GFG { static main() { let arr = [0, 1, 2, 3]; let r = 3; let com = new Combination(arr, r); com.GetFirst(); while (com.HasNext()) { com.Next(); } } } Â
if (require.main === module) { GFG.main(); } Â
// This code is contributed by lokeshpotta20. |
0 1 2 0 1 3 0 2 3 1 2 3
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!