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. 
C++
| // C++ implementation of the approach#include <iostream>usingnamespacestd;  classCombination {private:    // Data array for combination    int* Indices;      // Length of the data array    intN;      // Number of elements in the combination    intR;      // The boolean array    bool* Flags;      // Starting index of the 1st tract of trues    intStart;      // Ending index of the 1st tract of trues    intEnd;  public:    // Constructor    Combination(int* arr, intn, intr)    {        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    voidGetFirst()    {        this->Flags = newbool[N];          // Generate the very first combination        for(inti = 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    boolHasNext()    {        returnEnd < (this->N - 1);    }      // Function to generate the next combination    voidNext()    {          // 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(inti = this->Start; i <= this->End; ++i) {                    Flags[i] = false;                }                  // Set the beginning elements to true                for(inti = 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    voidOutput()    {        for(inti = 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 codeintmain(){    intarr[] = { 0, 1, 2, 3 };    intn = sizeof(arr) / sizeof(int);    intr = 3;    Combination com(arr, n, r);    com.GetFirst();    while(com.HasNext()) {        com.Next();    }    return0;} | 
Java
| // Java implementation of the approachclassCombination {      // Data array for combination    privateint[] Indices;      // Number of elements in the combination    privateintR;      // The boolean array    privateboolean[] Flags;      // Starting index of the 1st tract of trues    privateintStart;      // Ending index of the 1st tract of trues    privateintEnd;      // Constructor    publicCombination(int[] arr, intr)    {        this.Indices = arr;        this.R = r;    }      // Set the 1st r Booleans to true,    // initialize Start and End    publicvoidGetFirst()    {        Flags = newboolean[this.Indices.length];          // Generate the very first combination        for(inti = 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    publicbooleanHasNext()    {        returnEnd < (this.Indices.length - 1);    }      // Function to generate the next combination    publicvoidNext()    {          // 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(inti = this.Start; i <= this.End; ++i)                {                    Flags[i] = false;                }                  // Set the beginning elements to true                for(inti = 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    privatevoidOutput()    {        for(inti = 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 codeclassGFG {    publicstaticvoidmain(String[] args)    {        int[] arr = { 0, 1, 2, 3};        intr = 3;        Combination com = newCombination(arr, r);        com.GetFirst();        while(com.HasNext())        {            com.Next();        }    }}  // This code is contributed by Rajput-Ji | 
Python3
| # Python 3 implementation of the approachclassCombination :    # 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    defGetFirst(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) :        returnself.End < (len(self.Indices) -1)      Â    # Function to generate the next combination    defNext(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) andself.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    defOutput(self) :        i =0        count =0        while(i < len(self.Indices) andcount < 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 codeclassGFG :    @staticmethod    defmain( 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 approachusingSystem;namespaceIterativeCombination {classCombination {      // Data array for combination    privateint[] Indices;      // Number of elements in the combination    privateintR;      // The boolean array    privatebool[] Flags;      // Starting index of the 1st tract of trues    privateintStart;      // Ending index of the 1st tract of trues    privateintEnd;      // Constructor    publicCombination(int[] arr, intr)    {        this.Indices = arr;        this.R = r;    }      // Set the 1st r Booleans to true,    // initialize Start and End    publicvoidGetFirst()    {        Flags = newbool[this.Indices.Length];          // Generate the very first combination        for(inti = 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    publicboolHasNext()    {        returnEnd < (this.Indices.Length - 1);    }      // Function to generate the next combination    publicvoidNext()    {          // 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(inti = this.Start; i <= this.End; ++i) {                    Flags[i] = false;                }                  // Set the beginning elements to true                for(inti = 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    privatevoidOutput()    {        for(inti = 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 codeclassAppDriver {    staticvoidMain()    {        int[] arr = { 0, 1, 2, 3 };        intr = 3;        Combination com = newCombination(arr, r);        com.GetFirst();        while(com.HasNext()) {            com.Next();        }    }}} | 
Javascript
| //Javascript code for the above approachclass Combination {// Data array for combinationIndices = null;  // Number of elements in the combinationR = 0;  // The boolean arrayFlags = null;  // Starting index of the 1st tract of truesStart = 0;  // Ending index of the 1st tract of truesEnd = 0;  // Constructorconstructor(arr, r) {    this.Indices = arr;    this.R = r;}  // Set the 1st r Booleans to true,// initialize Start and EndGetFirst() {    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 generatedHasNext() {    returnthis.End < (this.Indices.length - 1);}  // Function to generate the next combinationNext() {    // 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 previousltOutput() {    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 previouslyif(this.Flags[i]) {document.write(this.Indices[i], " ");count += 1;}i += 1;}document.write("<br>");}}  // Driver codeclass GFG {static main() {let arr = [0, 1, 2, 3];let r = 3;let com = newCombination(arr, r);com.GetFirst();while(com.HasNext()) {com.Next();}}}  if(require.main === module) {GFG.main();} | 
Javascript
| //JS code for the above approachclass Combination {// Data array for combinationIndices = null;  // Number of elements in the combinationR = 0;  // The boolean arrayFlags = null;  // Starting index of the 1st tract of truesStart = 0;  // Ending index of the 1st tract of truesEnd = 0;  // Constructorconstructor(arr, r) {    this.Indices = arr;    this.R = r;}  // Set the 1st r Booleans to true,// initialize Start and EndGetFirst() {    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 generatedHasNext() {    returnthis.End < (this.Indices.length - 1);}  // Function to generate the next combinationNext(){      // 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 Endif(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 previouslyOutput() {    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 codeclass GFG {static main() {let arr = [0, 1, 2, 3];let r = 3;let com = newCombination(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!


 
                                    







