Iterative approach to print all combinations of an Array

19 June 2025

1

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.

Output:

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Iterative approach to print all combinations of an Array

C++

Java

Python3

C#

Javascript

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US