Subarray and Subsequence

Problem Statement

In the subarray and subsequence problem, we have to print all the subarrays and subsequences for a given array. Generate all possible non-empty subarrays. A subarray is commonly defined as a part or section of an array in which the contiguousness is based on the index. The subarray is inside another array. For an array of size n, there will be n*(n+1)/2 non-empty subarray.

Example

4
1 2 3 4

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

Algorithm for Subarrays

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

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

2. In the first loop pick a starting point (i) from 0 to n

3. pick ending point (j) from i to n

4. print elements between i and j.

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

Implementation

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;
}

All possible non-empty subarrays
[1,]
[1,2,]
[1,2,3,]
[1,2,3,4,]
[2,]
[2,3,]
[2,3,4,]
[3,]
[3,4,]
[4,]

Java Program

import java.util.Scanner;
class sum
{
    // Prints all subarrays in arr[0..n-1]
    public static 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
                System.out.print("[");
                for (int k=i; k<j; k++)
                {
                        System.out.print(arr[k]+",");
                    }
                System.out.println(arr[j]+"]");
            }
        }
        
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        PrintAllSubarrays(a,n);
        System.out.println();
    }
}

3
1 2 3

[1]
[1,2]
[1,2,3]
[2]
[2,3]
[3]

Complexity Analysis for Subarray

Time Complexity

O(n*n*n) where n is the size of the array. Here we run two for loops for the starting and ending point of the subarray. Now run one more for loop inside the two for loop to print the answer. Here we run three nested for loops which meantime complexity will be O(n*n*n).

Space Complexity

O(1) because we just print the values without storing the result. Here we don’t use any auxiliary space.

Generate all possible non-empty sub-sequences. A subsequence is a part of an array which is a 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.

1 2 3 4

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

Algorithm for subsequences

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

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 the ith bit in the counter is set, print ith element for these subsequences.
4. Start a new subsequence in the new line.

3. Call this function on a given input array to print all the possible sub-sequences.

Implementation

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;
}

import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
    //using counter to print all possible sub-sequences
    public static void PrintAllSubarrays(int array[], int N)
    {
        //total number of possible non-empty sub-sequences
        int set_size = (int) pow(2, N) ;
        for (int i = 1; i < set_size; i++)
        {
            //printing subsequence
            System.out.print("[");
            for(int j = 0; j < N-1; j++)
            {
                int temp = (int) (1<<j);
                if( (i & temp) > 0)
                {
                    System.out.print(array[j]+",");
                }
            }
            System.out.println(array[N-1]+"]");
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        PrintAllSubarrays(a,n);
        System.out.println();
    }
}

3
1 2 3

[1,3]
[2,3]
[1,2,3]
[3]
[1,3]
[2,3]
[1,2,3]