Subarray and Subsequence

Generate all possible non-empty subarrays.

A subarray is commonly defined as a part or section of an array which the contiguousness is based on the index. Subarray is inside another array.
For an array of size n, there will be n*(n+1)/2 non-empty subarrays.

Examples

Input array [1, 2, 3, 4]

Output

All non-empty subarrays are


 1
 1, 2
 1, 2, 3
 1, 2, 3, 4
 2
 2, 3
 2, 3, 4
 3
 3, 4
 4

Time Complexity : O(n^3)

Algorithm

Idea : Run two nested loops picking the start point and endpoint, and print all the elements.

Step 1 : Create a function which takes the input array and prints all the non-empty subarrays.

Step 2 : In first loop pick starting point (i) from 0 to n

Step 3 : pick ending point (j) from i to n

Step 4 : print elements between i and j.

Step 5 : call the function on given array to print all the possible non-empty subarrays.

Algorithm working

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
// Prints all subarrays in arr[0..n-1]
void PrintAllSubarrays(int arr[], int n)
{
    //starting point
    for (int i=0; i <n; i++)
    {
        //ending point
        for (int j=i; j<n; j++)
        {
            //Printing elements between the start and end points
            cout<<"[";
            for (int k=i; k<=j; k++)
                {
                    cout<<arr[k]<<",";
                }
            cout<<"]"<<endl;
        }
    }
}
//Main function
int main()
{
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "All possible non-empty subarrays\n";
    PrintAllSubarrays(arr, n);
    return 0;
}
Try It

Subsequence

Generate all possible non-empty sub-sequences.

A subsequence is a part of an array which is sequence that is derived from another sequence by deleting some elements without changing the order.

For an array of size n, there will be 2n-1 non-empty sub-sequences possible.

Examples

Input array : [1,2,3,4]

Output : All non-empty sub-sequences are


 1
 2
 3
 4
 1, 2
 1, 3
 1, 4
 2, 3
 2, 4,
 3, 4
 1, 2, 3
 1, 3, 4
 1, 2, 4
 2, 3, 4
1, 2, 3, 4

Time Complexity : O(n * 2n)

Algorithm

Step 1 : Create a function to print all the possible subarrays.

Step 2 : In the function,

  1. Store the total number of possible sub-sequences in size.
  2. Run a loop from 0 to size.
  3. Loop from 0 to n and if ith bit in counter is set, print ith element for this subsequnce.
  4. Start a new subsequence in new line.

Step 3 : call this function on given input array to print all the possible sub-sequences.

Algorithm working

C++ Program

#include <bits/stdc++.h>
using namespace std;

//using counter to print all possible sub-sequences
void PrintAllSubsequences(int array[], int N)
{
    //total number of possible non-empty sub-sequences
    unsigned int set_size = pow(2, N) - 1 ;
    for (int i = 1; i < set_size; i++)
    {
        //printing subsequence
        cout<<"[";
        for (int j = 0; j <= N; j++)
        {
            if(i & (1<<j))
                {
                    cout<<array[j]<<",";
                }
        }
        cout<<"]"<<endl;
    }
}
 
//Main function
int main()
{
    int array[] = {1, 2, 3, 4};
    int N = sizeof(array)/sizeof(array[0]);
    cout << "All non-empty sub-sequences are:\n";
    PrintAllSubsequences(array, N);
    return 0;
}
Try It


Next > < Prev
Scroll to Top