Working Code Examples
Below is the implementation to print subsequence’s of an array:
C++
#include <iostream> #include <vector> void printSubsequences(std::vector< int >& arr, int index, std::vector< int >& subsequence) { if (index == arr.size()) { for ( int i = 0; i < subsequence.size(); i++) { std::cout << subsequence[i] << " "; } std::cout << std::endl; return ; } // Include the current element subsequence.push_back(arr[index]); printSubsequences(arr, index + 1, subsequence); // Exclude the current element subsequence.pop_back(); printSubsequences(arr, index + 1, subsequence); } int main() { std::vector< int > arr = { 1, 2, 3 }; std::vector< int > subsequence; std::cout << "Subsequences:" << std::endl; printSubsequences(arr, 0, subsequence); return 0; } |
C
#include <stdio.h> void printSubsequences( int arr[], int n, int index, int subsequence[], int subLength) { if (index == n) { for ( int i = 0; i < subLength; i++) { printf ("%d ", subsequence[i]); } printf ("\n"); return ; } // Include the current element subsequence[subLength] = arr[index]; printSubsequences(arr, n, index + 1, subsequence, subLength + 1); // Exclude the current element printSubsequences(arr, n, index + 1, subsequence, subLength); } int main() { int arr[] = {1, 2, 3}; int n = sizeof (arr) / sizeof (arr[0]); int subsequence[n]; // Maximum possible length printf ("Subsequences:\n"); printSubsequences(arr, n, 0, subsequence, 0); return 0; } |
Java
public class SubsequenceExample { public static void printSubsequences( int [] arr, int index, List<Integer> subsequence) { if (index == arr.length) { for ( int num : subsequence) { System.out.print(num + " "); } System.out.println(); return ; } // Include the current element subsequence.add(arr[index]); printSubsequences(arr, index + 1 , subsequence); subsequence.remove(subsequence.size() - 1 ); // Exclude the current element printSubsequences(arr, index + 1 , subsequence); } public static void main(String[] args) { int [] arr = { 1 , 2 , 3 }; List<Integer> subsequence = new ArrayList<>(); System.out.println("Subsequences:"); printSubsequences(arr, 0 , subsequence); } } |
Python3
def print_subsequences(arr, index, subsequence): if index = = len (arr): print ( * subsequence) return # Include the current element subsequence.append(arr[index]) print_subsequences(arr, index + 1 , subsequence) subsequence.pop() # Backtrack # Exclude the current element print_subsequences(arr, index + 1 , subsequence) if __name__ = = "__main__": arr = [ 1 , 2 , 3 ] subsequence = [] print ("Subsequences:") print_subsequences(arr, 0 , subsequence) |
C#
using System; using System.Collections.Generic; class Program { // Function to print all subsequences of an array static void PrintSubsequences(List< int > arr, int index, List< int > subsequence) { // If index reaches the end of the array, print the current subsequence if (index == arr.Count) { foreach ( int num in subsequence) { Console.Write(num + " " ); } Console.WriteLine(); return ; } // Include the current element in the subsequence subsequence.Add(arr[index]); PrintSubsequences(arr, index + 1, subsequence); // Exclude the current element from the subsequence subsequence.RemoveAt(subsequence.Count - 1); PrintSubsequences(arr, index + 1, subsequence); } static void Main() { // Input array List< int > arr = new List< int > { 1, 2, 3 }; // List to store the current subsequence List< int > subsequence = new List< int >(); // Print all subsequences Console.WriteLine( "Subsequences:" ); PrintSubsequences(arr, 0, subsequence); } } |
Javascript
function printSubsequences(arr, index, subsequence) { if (index === arr.length) { console.log(subsequence.join( ' ' )); return ; } // Include the current element subsequence.push(arr[index]); printSubsequences(arr, index + 1, subsequence); subsequence.pop(); // Backtrack // Exclude the current element printSubsequences(arr, index + 1, subsequence); } const arr = [1, 2, 3]; const subsequence = []; console.log("Subsequences:"); printSubsequences(arr, 0, subsequence); |
Subsequences: 1 2 3 1 2 1 3 1 2 3 2 3
Time Complexity: O(2N)
Auxiliary Space Complexity: O(N)
Conclusion
Subsequences in arrays are a powerful concept used in various domains, offering insights into data, patterns, and optimization problems. Understanding their definition, use cases, and best practices is crucial for efficient problem-solving. While working with subsequence’s can be challenging, the solutions to common problems are often rooted in dynamic programming, recursion, or clever algorithms. Explore and experiment with subsequence’s to unlock their potential in your programming endeavours.
What are Subsequences in an Array?
Subsequences are a fundamental concept in computer science and programming when working with arrays. A subsequence of an array is a sequence of elements from the array that appear in the same order, but not necessarily consecutively. In this blog post, we’ll discuss subsequences, covering their definition, use cases, examples, when to use them, when not to use them, best practices, and common problems, and provide working code examples in C, C++, Java, Python, and JavaScript.
Table of Content
- Definition and Full Form
- Use Cases
- Examples
- When to Use Subsequences
- When Not to Use Subsequences
- Best Practices
- Common Problems and Solutions
- Working Code Examples
- Conclusion
Contact Us