Skip to main content

Generating all sub-sequence of an array of limited size

In this article, we will discuss how to generate all sub-sequences of an array with a limited size. A sub-sequence of an array is a sequence of elements taken from the original array, preserving their relative order.

Problem Statement

Given an array of integers and a limit on the size of sub-sequences, we want to generate all possible sub-sequences that satisfy the given limit.

Example

Let's consider the following examples to understand the problem better:

Example 1:

Input:  [1, 2, 3, 6]
Limit:  3

Output:
1
2
1 2
3
1 3
2 3
1 2 3
6
1 6
2 6
1 2 6
3 6
1 3 6
2 3 6
1 2 3 6

Example 2:

Input:  [7, 8, 1, 6, 4]
Limit:  4

Output:
7
8
7 8
1
7 1
8 1
7 8 1
6
7 6
8 6
7 8 6
1 6
7 1 6
8 1 6
7 8 1 6
4
7 4
8 4
7 8 4
1 4
7 1 4
8 1 4
7 8 1 4
6 4
7 6 4
8 6 4
7 8 6 4
1 6 4
7 1 6 4
8 1 6 4
7 8 1 6 4

Algorithm

To generate all sub-sequences of an array, we can use a binary counting technique. The idea is to use a binary representation of numbers from 1 to 2^n - 1, where n is the size of the array.

The steps of the algorithm are as follows:

  1. Create an empty list to store each sub-sequence.
  2. Iterate from 1 to 2^n - 1.
  3. For each number, iterate over the array elements.
  4. If the bit at the corresponding index is set, add the element to the sub-sequence list.
  5. Print the sub-sequence list.
  6. Clear the sub-sequence list for the next iteration.

Pseudocode


function printSubArray(record):
    for i = 0 to record.length - 1:
        print record[i]
    end for
end function

function findSubArray(arr, n):
    record = empty list
    for i = 1 to (1 << n) - 1:
        for j = 0 to n - 1:
            if (i & (1 << j)) > 0:
                record.add(arr[j])
            end if
        end for
        printSubArray(record)
        clear record
    end for
end function

function main():
    arr1 = [1, 2, 3, 6]
    arr2 = [7, 8, 1, 6, 4]

    n = length of arr1
    findSubArray(arr1, n)

    n = length of arr2
    findSubArray(arr2, n)
end function

main()

Explanation

The algorithm uses nested loops to generate all possible sub-sequences. The outer loop iterates from 1 to 2^n - 1, where n is the size of the array. This loop generates all possible binary representations from 1 to 2^n - 1.

The inner loop iterates over the array elements. It checks if the corresponding bit is set in the binary representation of the outer loop's counter. If the bit is set, the element at that index is added to the sub-sequence list.

After adding the elements to the sub-sequence list, it is printed, and then the list is cleared for the next iteration.

Code Solution

// Java program for
// Generating all sub-sequence of an array of limited size
import java.util.ArrayList;

public class SubSequence
{
    public void printSubArray(ArrayList < Integer > record)
    {
        // Print record elements
        for (int i = 0; i < record.size(); i++)
        {
            System.out.print(" " + record.get(i));
        }
    
    }
    public void findSubArray(int []arr, int n)
    {

        // Use to collect information of sub-sequence
        ArrayList < Integer > record = new ArrayList < Integer > ();

        for (int i = 1; i < (1 << n); i++)
        {
            // This loop are generating all sub-sequence
            for (int j = 0; j < n; j++)
            {
                if ((i & (1 << j)) > 0)
                {
                    // Add sub-sequence element
                    record.add(arr[j]);
                }
            }
            // Display sub array element
            printSubArray(record);

            // Add new line
            System.out.print("\n");

            // Remove all record element
            record.clear();
        }
        System.out.print("\n");
    }
    public static void main(String[] args)
    {
        SubSequence task = new SubSequence();

        int []arr1 = 
        {
            1 , 2 , 3 , 6
        };
        int []arr2 = 
        {
            7 , 8 , 1 , 6, 4
        };

        // Test Case A
        int n = arr1.length;
        task.findSubArray(arr1, n);

        // Test Case B
        n = arr2.length;
        task.findSubArray(arr2, n);
    }
}

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4

// Include header file
#include <iostream>
#include <vector>
using namespace std;

// C++ program for
// Generating all sub-sequence of an array of limited size

class SubSequence
{
	public: void printSubArray(vector < int > record)
	{
		// Print record elements
		for (int i = 0; i < record.size(); i++)
		{
			cout << " " << record.at(i);
		}
	}
	void findSubArray(int arr[], int n)
	{
		// Use to collect information of sub-sequence
		vector < int > record ;
		for (int i = 1; i < (1 << n); i++)
		{
			// This loop are generating all sub-sequence
			for (int j = 0; j < n; j++)
			{
				if ((i &(1 << j)) > 0)
				{
					// Add sub-sequence element
					record.push_back(arr[j]);
				}
			}
			// Display sub array element
			this->printSubArray(record);
			// Add new line
			cout << "\n";
			// Remove all record element
			record.clear();
		}
		cout << "\n";
	}
};
int main()
{
	SubSequence *task = new SubSequence();
	int arr1[] = {
		1 , 2 , 3 , 6
	};
	int arr2[] = {
		7 , 8 , 1 , 6 , 4
	};
	// Test Case A
	int n = sizeof(arr1) / sizeof(arr1[0]);
	task->findSubArray(arr1, n);
	// Test Case B
	n = sizeof(arr2) / sizeof(arr2[0]);
	task->findSubArray(arr2, n);
	return 0;
}

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4

// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Generating all sub-sequence of an array of limited size
public class SubSequence
{
	public void printSubArray(List < int > record)
	{
		// Print record elements
		for (int i = 0; i < record.Count; i++)
		{
			Console.Write(" " + record[i]);
		}
	}
	public void findSubArray(int[] arr, int n)
	{
		// Use to collect information of sub-sequence
		List < int > record = new List < int > ();
		for (int i = 1; i < (1 << n); i++)
		{
			// This loop are generating all sub-sequence
			for (int j = 0; j < n; j++)
			{
				if ((i & (1 << j)) > 0)
				{
					// Add sub-sequence element
					record.Add(arr[j]);
				}
			}
			// Display sub array element
			this.printSubArray(record);
			// Add new line
			Console.Write("\n");
			// Remove all record element
			record.Clear();
		}
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		SubSequence task = new SubSequence();
		int[] arr1 = {
			1 , 2 , 3 , 6
		};
		int[] arr2 = {
			7 , 8 , 1 , 6 , 4
		};
		// Test Case A
		int n = arr1.Length;
		task.findSubArray(arr1, n);
		// Test Case B
		n = arr2.Length;
		task.findSubArray(arr2, n);
	}
}

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4

<?php
// Php program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
	public	function printSubArray($record)
	{
		// Print record elements
		for ($i = 0; $i < count($record); $i++)
		{
			echo(" ".$record[$i]);
		}
	}
	public	function findSubArray($arr, $n)
	{
		// Use to collect information of sub-sequence
		$record = array();
		for ($i = 1; $i < (1 << $n); $i++)
		{
			// This loop are generating all sub-sequence
			for ($j = 0; $j < $n; $j++)
			{
				if (($i & (1 << $j)) > 0)
				{
					// Add sub-sequence element
					$record[] = $arr[$j];
				}
			}
			// Display sub array element
			$this->printSubArray($record);
			// Add new line
			echo("\n");
			// Remove all record element
			$record = array();
		}
		echo("\n");
	}
}

function main()
{
	$task = new SubSequence();
	$arr1 = array(1, 2, 3, 6);
	$arr2 = array(7, 8, 1, 6, 4);
	// Test Case A
	$n = count($arr1);
	$task->findSubArray($arr1, $n);
	// Test Case B
	$n = count($arr2);
	$task->findSubArray($arr2, $n);
}
main();

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4

// Node JS program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
	printSubArray(record)
	{
		// Print record elements
		for (var i = 0; i < record.length; i++)
		{
			process.stdout.write(" " + record[i]);
		}
	}
	findSubArray(arr, n)
	{
		// Use to collect information of sub-sequence
		var record = [];
		for (var i = 1; i < (1 << n); i++)
		{
			// This loop are generating all sub-sequence
			for (var j = 0; j < n; j++)
			{
				if ((i & (1 << j)) > 0)
				{
					// Add sub-sequence element
					record.push(arr[j]);
				}
			}
			// Display sub array element
			this.printSubArray(record);
			// Add new line
			process.stdout.write("\n");
			// Remove all record element
			record = [];
		}
		process.stdout.write("\n");
	}
}

function main()
{
	var task = new SubSequence();
	var arr1 = [1, 2, 3, 6];
	var arr2 = [7, 8, 1, 6, 4];
	// Test Case A
	var n = arr1.length;
	task.findSubArray(arr1, n);
	// Test Case B
	n = arr2.length;
	task.findSubArray(arr2, n);
}
main();

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4

#  Python 3 program for
#  Generating all sub-sequence of an array of limited size
class SubSequence :
	def printSubArray(self, record) :
		#  Print record elements
		i = 0
		while (i < len(record)) :
			print(" ", record[i], end = "")
			i += 1
		
	
	def findSubArray(self, arr, n) :
		#  Use to collect information of sublist
		record = []
		i = 1
		while (i < (1 << n)) :
			
			j = 0
			#  This loop are generating all sublists
			while (j < n) :
				if ((i & (1 << j)) > 0) :
					#  Add sublist element
					record.append(arr[j])
				
				j += 1
			
			#  Display sub list element
			self.printSubArray(record)
			#  Add new line
			print(end = "\n")
			#  Remove all record element
			record.clear()
			i += 1
		
		print(end = "\n")
	

def main() :
	task = SubSequence()
	arr1 = [1, 2, 3, 6]
	arr2 = [7, 8, 1, 6, 4]
	#  Test Case A
	n = len(arr1)
	task.findSubArray(arr1, n)
	#  Test Case B
	n = len(arr2)
	task.findSubArray(arr2, n)

if __name__ == "__main__": main()

input

  1
  2
  1  2
  3
  1  3
  2  3
  1  2  3
  6
  1  6
  2  6
  1  2  6
  3  6
  1  3  6
  2  3  6
  1  2  3  6

  7
  8
  7  8
  1
  7  1
  8  1
  7  8  1
  6
  7  6
  8  6
  7  8  6
  1  6
  7  1  6
  8  1  6
  7  8  1  6
  4
  7  4
  8  4
  7  8  4
  1  4
  7  1  4
  8  1  4
  7  8  1  4
  6  4
  7  6  4
  8  6  4
  7  8  6  4
  1  6  4
  7  1  6  4
  8  1  6  4
  7  8  1  6  4

#  Ruby program for
#  Generating all sub-sequence of an array of limited size
class SubSequence 
	def printSubArray(record) 
		i = 0
		#  Print record elements
		while (i < record.length) 
			print(" ", record[i])
			i += 1
		end

	end

	def findSubArray(arr, n) 
		#  Use to collect information of sub-sequence
		record = []
		i = 1
		while (i < (1 << n)) 
			#  This loop are generating all sub-sequence
			j = 0
			while (j < n) 
				if ((i & (1 << j)) > 0) 
					#  Add sub-sequence element
					record.push(arr[j])
				end

				j += 1
			end

			#  Display sub array element
			self.printSubArray(record)
			#  Add new line
			print("\n")
			#  Remove all record element
			record.clear()
			i += 1
		end

		print("\n")
	end

end

def main() 
	task = SubSequence.new()
	arr1 = [1, 2, 3, 6]
	arr2 = [7, 8, 1, 6, 4]
	#  Test Case A
	n = arr1.length
	task.findSubArray(arr1, n)
	#  Test Case B
	n = arr2.length
	task.findSubArray(arr2, n)
end

main()

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4


import scala.collection.mutable._;
// Scala program for
// Generating all sub-sequence of an array of limited size
class SubSequence()
{
	def printSubArray(record: ArrayBuffer[Int]): Unit = {
	
		var i: Int = 0;
      	// Print record elements
		while (i < record.size)
		{
			print(" " + record(i));
			i += 1;
		}
	}
	def findSubArray(arr: Array[Int], n: Int): Unit = {
		// Use to collect information of sub-sequence
		var record: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		var i: Int = 1;
		while (i < (1 << n))
		{
			var j: Int = 0;
          	// This loop are generating all sub-sequence
			while (j < n)
			{
				if ((i & (1 << j)) > 0)
				{
					// Add sub-sequence element
					record += arr(j);
				}
				j += 1;
			}
			// Display sub array element
			printSubArray(record);
			// Add new line
			print("\n");
			// Remove all record element
			record.clear();
			i += 1;
		}
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: SubSequence = new SubSequence();
		var arr1: Array[Int] = Array(1, 2, 3, 6);
		var arr2: Array[Int] = Array(7, 8, 1, 6, 4);
		// Test Case A
		var n: Int = arr1.length;
		task.findSubArray(arr1, n);
		// Test Case B
		n = arr2.length;
		task.findSubArray(arr2, n);
	}
}

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4

import Foundation;
// Swift 4 program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
	func printSubArray(_ record: [Int])
	{
		// Print record elements
		var i = 0;
		while (i < record.count)
		{
			print(" ", record[i], terminator: "");
			i += 1;
		}
	}
	func findSubArray(_ arr: [Int], _ n: Int)
	{
		// Use to collect information of sub-sequence
		var record = [Int]();
		var i = 1;
		while (i < (1 << n))
		{
			
			var j = 0;
          	// This loop are generating all sub-sequence
			while (j < n)
			{
				if ((i & (1 << j)) > 0)
				{
					// Add sub-sequence element
					record.append(arr[j]);
				}
				j += 1;
			}
			// Display sub array element
			self.printSubArray(record);
			// Add new line
			print(terminator: "\n");
			// Remove all record element
			record.removeAll();
			i += 1;
		}
		print(terminator: "\n");
	}
}
func main()
{
	let task = SubSequence();
	let arr1 = [1, 2, 3, 6];
	let arr2 = [7, 8, 1, 6, 4];
	// Test Case A
	var n = arr1.count;
	task.findSubArray(arr1, n);
	// Test Case B
	n = arr2.count;
	task.findSubArray(arr2, n);
}
main();

input

  1
  2
  1  2
  3
  1  3
  2  3
  1  2  3
  6
  1  6
  2  6
  1  2  6
  3  6
  1  3  6
  2  3  6
  1  2  3  6

  7
  8
  7  8
  1
  7  1
  8  1
  7  8  1
  6
  7  6
  8  6
  7  8  6
  1  6
  7  1  6
  8  1  6
  7  8  1  6
  4
  7  4
  8  4
  7  8  4
  1  4
  7  1  4
  8  1  4
  7  8  1  4
  6  4
  7  6  4
  8  6  4
  7  8  6  4
  1  6  4
  7  1  6  4
  8  1  6  4
  7  8  1  6  4

// Kotlin program for
// Generating all sub-sequence of an array of limited size
class SubSequence
{
	fun printSubArray(record: MutableList < Int >  ): Unit
	{
		// Print record elements
		var i: Int = 0;
		while (i < record.size)
		{
			print(" " + record[i]);
			i += 1;
		}
	}
	fun findSubArray(arr: Array < Int > , n: Int): Unit
	{
		// Use to collect information of sub-sequence
		val record: MutableList < Int > = mutableListOf < Int > ();
		var i: Int = 1;
		while (i < (1 shl n))
		{
			// This loop are generating all sub-sequence
			var j: Int = 0;
			while (j < n)
			{
				if ((i and (1 shl j)) > 0)
				{
					// Add sub-sequence element
					record.add(arr[j]);
				}
				j += 1;
			}
			// Display sub array element
			this.printSubArray(record);
			// Add new line
			print("\n");
			// Remove all record element
			record.clear();
			i += 1;
		}
		print("\n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: SubSequence = SubSequence();
	val arr1: Array < Int > = arrayOf(1, 2, 3, 6);
	val arr2: Array < Int > = arrayOf(7, 8, 1, 6, 4);
	// Test Case A
	var n: Int = arr1.count();
	task.findSubArray(arr1, n);
	// Test Case B
	n = arr2.count();
	task.findSubArray(arr2, n);
}

input

 1
 2
 1 2
 3
 1 3
 2 3
 1 2 3
 6
 1 6
 2 6
 1 2 6
 3 6
 1 3 6
 2 3 6
 1 2 3 6

 7
 8
 7 8
 1
 7 1
 8 1
 7 8 1
 6
 7 6
 8 6
 7 8 6
 1 6
 7 1 6
 8 1 6
 7 8 1 6
 4
 7 4
 8 4
 7 8 4
 1 4
 7 1 4
 8 1 4
 7 8 1 4
 6 4
 7 6 4
 8 6 4
 7 8 6 4
 1 6 4
 7 1 6 4
 8 1 6 4
 7 8 1 6 4

Output Explanation

For example 1, the input array is [1, 2, 3, 6] with a limit of 3. The algorithm generates all sub-sequences of length 1, 2, and 3. The output shows all the generated sub-sequences.

Similarly, for example 2, the input array is [7, 8, 1, 6, 4] with a limit of 4. The algorithm generates all sub-sequences of length 1, 2, 3, and 4. The output displays all the generated sub-sequences.

Time Complexity

The time complexity of this algorithm is O(2^n * n), where n is the size of the input array. The outer loop runs 2^n - 1 times, and the inner loop iterates over n elements. Hence, the overall time complexity is exponential but bounded by the size of the input array.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment