Generating All Subsequences of an Array Using Recursion

Introduction

In many programming interview problems you are asked to list or count subsequences of a given array. Unlike subarrays, subsequences do not need to be contiguous; they only need to preserve the original order of elements. This article explains the concept of subsequences and shows a clean recursive solution that generates every possible subsequence for an array of size n.

What Is a Subsequence?

• A subsequence is any sequence that can be derived from the original array by deleting zero or more elements without changing the relative order of the remaining elements.
• Examples for the array [3, 1, 2]:
• [3], [1], [2] – single‑element subsequences
• [3, 1], [1, 2], [3, 2] – two‑element subsequences (note that [3, 2] is non‑contiguous)
• [3, 1, 2] – the whole array
• [] – the empty subsequence (picking no elements)
• A subarray is a special case of a subsequence that must be contiguous. Every subarray is a subsequence, but not every subsequence is a subarray.

Recursive Insight – "Take or Not Take"

For each index i in the array you have exactly two choices: 1. Take the element at i and add it to the current subsequence. 2. Do not take the element at i and leave the current subsequence unchanged. By applying this binary decision at every position, you explore all 2^n possible subsets.

Recursive Algorithm Structure

function generate(idx, current):
    if idx == n:                // base case – processed all elements
        print current
        return
    // Choice 1: take arr[idx]
    current.add(arr[idx])
    generate(idx + 1, current)
    current.removeLast()        // backtrack
    // Choice 2: do not take arr[idx]
    generate(idx + 1, current)

Key points: - Base case triggers when the index reaches the length of the array; the built subsequence is printed. - After the take branch returns, we remove the last added element (backtracking) so that the not‑take branch starts from the correct state. - The data structure (vector in C++, ArrayList in Java, or a Python list) is passed by reference to avoid copying at each call.

Step‑by‑Step Walkthrough for [3, 1, 2]

1. Start with idx = 0, current = [].
2. Take 3 → current = [3], recurse with idx = 1.
3. Take 1 → current = [3,1], recurse with idx = 2.
   • Take 2 → current = [3,1,2] → print [3,1,2].
   • Backtrack, Not take 2 → print [3,1].
4. Backtrack, Not take 1 → current = [3].
   • Take 2 → print [3,2].
   • Not take 2 → print [3].
5. Backtrack to the very first level, Not take 3 → current = [].
6. Repeat the same two‑choice process for indices 1 and 2, producing [1,2], [1], [2], and []. The recursion tree therefore yields all eight subsequences.

Recursion Tree Visualisation

                f(0, [])
           /                \
      take 3               not‑take 3
      f(1,[3])                f(1,[])
     /      \                /      \
  take1   not1          take1   not1
 ...      ...            ...      ...

Each leaf node corresponds to a completed subsequence.

Implementation Tips

• Pass the container by reference (e.g., vector<int>& ds) to avoid costly copies.
• Use push_back / add for the take step and pop_back / remove for backtracking.
• Printing can be done directly in the base case; optionally collect results in a list of lists.
• The order of output depends on whether you explore the take branch before the not‑take branch (or vice‑versa).

Complexity Analysis

• Time Complexity: O(2^n * n) – there are 2^n subsequences, and printing each subsequence takes up to O(n) time.
• Space Complexity: O(n) – the recursion depth equals the array length, plus the temporary container that holds at most n elements.

When to Use This Approach

• Perfect for interview questions that ask for all subsequences or for counting them.
• The same "take / not‑take" pattern extends to many combinatorial problems (subsets, permutations with constraints, etc.).

Quick Reference Code (C++)

void generate(int idx, const vector<int>& arr, vector<int>& cur){
    if(idx == arr.size()){
        for(int x:cur) cout<<x<<" ";
        cout<<"\n"; // prints empty line for []
        return;
    }
    // take
    cur.push_back(arr[idx]);
    generate(idx+1, arr, cur);
    cur.pop_back(); // backtrack
    // not take
    generate(idx+1, arr, cur);
}

A similar Java version uses ArrayList<Integer> and add/remove.

Summary of the Core Idea

• Binary decision at each index (take / not take) generates the power set of the array.
• Backtracking (removing the last element) restores the state for the alternative branch.
• The method works for any array size and naturally yields 2^n subsequences.

By applying a simple recursive "take or not take" strategy and proper backtracking, you can generate all 2ⁿ subsequences of an array in O(2ⁿ·n) time and O(n) auxiliary space, making it a fundamental technique for many combinatorial programming problems.