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
Input
arr[] = {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
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.
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,]
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.
Input
arr = {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
Algorithm for subsequences
1. Create a function to print all the possible subarrays.
2. In the function,
- Store the total number of possible sub-sequences in size.
- Run a loop from 0 to size.
- Loop from 0 to n and if the ith bit in the counter is set, print ith element for these subsequences.
- Start a new subsequence in the new line.
3. Call this function on a given input array to print all the possible sub-sequences.
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; }
All non-empty sub-sequences are: [1,] [2,] [1,2,] [3,] [1,3,] [2,3,] [1,2,3,] [4,] [1,4,] [2,4,] [1,2,4,] [3,4,] [1,3,4,] [2,3,4,]
Complexity Analysis for Subsequence
Time Complexity
O(2^n) where n is the size of the array. Time complexity is exponential because we print all possible subsequences here.
Space Complexity
O(1) because we just print the values without storing the result. Here we don’t use any auxiliary space.