DAY 13 : Mastering Subsequence Recursion in Java | My DSA Journey (Recursion)

---

Introduction

Welcome to Day 13 of my DSA Journey!
For the past few days, I’ve been focusing on one of the most fundamental and important concepts in DSA — Recursion.

Solved some basic subsequences questions which helps me to understand how to explore and generate all possible combinations of an array or string using recursion.

I’m documenting my journey in public to stay consistent and to help others who are also learning DSA from scratch.

Here’s what I learnt in last 3 days:

• Day 10:
  → Print all Subsequences of:

  • array
  • string

• Day 11:
  → Count all subsequences with sum K
  → Check if there exists a subsequence with sum K

• Day 12:
  → Subset Sum

Let’s break down each of these topics below 👇

---

Q 1. Print all Subsequences of array:

In this problem, we are given an array of integers, and we need to print all possible subsequences of this array.

What is a Subsequence?

A subsequence is a sequence that can be derived from the array by either picking or not picking each element, maintaining the original order.

It doesn’t need to be contiguous, but it must follow the same relative order as the original array.

Example:

For array: [1, 2, 3]

All possible subsequences are:

• [1, 2, 3]
• [1, 2]
• [1, 3]
• [1]
• [2, 3]
• [2]
• [3]
• [] (empty subsequence)

There are 2^n subsequences for an array of size n.

Approach: Recursion + Pick / Not Pick

We'll use a recursive approach where for each element, we have two choices:

1. Pick the current element and move to the next index.
2. Don't pick the current element and move to the next index.

This creates a binary tree of choices, covering all combinations.

Recursive Tree Visualization (Pick / Not Pick)

Let's say the input array is: [1, 2, 3]

                            []
                          /    \
                        [1]     []
                       /   \     /   \
                   [1,2]  [1]  [2]   []
                  /   \   /    \   /  \
            [1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

In the end, we get all combinations (i.e. subsequences):
[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []

Total subsequences: 2^n = 2^3 = 8

Example:

Let’s dry run for: arr = [1, 2, 3]

Step-by-step breakdown:

1. Start with []

2. ✅ Pick 1 → [1]

   • ✅ Pick 2 → [1, 2]
     • ✅ Pick 3 → [1, 2, 3] ✅
     • ❌ Not Pick 3 → [1, 2] ✅
   • ❌ Not Pick 2 → [1]
     • ✅ Pick 3 → [1, 3] ✅
     • ❌ Not Pick 3 → [1] ✅

3. ❌ Not Pick 1 → []

   • ✅ Pick 2 → [2]
     • ✅ Pick 3 → [2, 3] ✅
     • ❌ Not Pick 3 → [2] ✅
   • ❌ Not Pick 2 → []
     • ✅ Pick 3 → [3] ✅
     • ❌ Not Pick 3 → [] ✅

All Subsequences Generated:

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

Code:

static void printSubSeqArr(ArrayList<Integer> list, int[] arr, int index) {
    if (index >= arr.length) {
        System.out.println(list);
        return;
    }

    // Pick the current element
    list.add(arr[index]);
    printSubSeqArr(list, arr, index + 1);

    // Backtrack (remove the picked element)
    list.removeLast();

    // Do not pick the current element
    printSubSeqArr(list, arr, index + 1);
}

---

Q 2. Print all Subsequences of string:

This question is almost identical to our previous problem where we printed all subsequences of an array using recursion.

Here, instead of an array of integers, we are given a string, and we need to print all its subsequences.

What is a Subsequence?

A subsequence of a string is a new string generated by including or excluding each character in order.

For example, for "abc", the subsequences are:
a, b, c, ab, ac, bc, abc, ""

Approach:

We apply the same Pick / Not Pick recursive pattern:

• At each index, we have two choices:
  • ✅ Pick the current character and add it to the result.
  • ❌ Not pick it and move forward.

This leads to 2^n possible subsequences for a string of length n.

Recursive Tree Visualization:

Let's say the input string is: abc

                    ""
                  /    \
               "a"     ""
             /    \    /   \
         "ab"   "a"  "b"   ""
        /   \   / \  / \   / \
    "abc" "ab" "ac" "a" "bc" "b" "c" ""

Final Subsequences Collected: abc, ab, ac, a, bc, b, c, ""

Code:

public class Main {

    static void printSubSeq(String p, String up) {
        if (up.isEmpty()) {
            if (p.isEmpty()) {
                System.out.print("{} "); // Representing empty subsequence
                return;
            }
            System.out.print(p + " ");
            return;
        }

        char ch = up.charAt(0);

        // Pick the character
        printSubSeq(p + ch, up.substring(1));

        // Not pick the character
        printSubSeq(p, up.substring(1));
    }

    public static void main(String[] args) {
        String str = "abc";
        printSubSeq("", str);
    }
}

---

Q 3. Count all subsequences with sum K:

Given an array of integers and a target sum K, count all subsequences whose sum is exactly equal to K.

Example:

Input: arr = [1, 2, 1], target = 2
Output: 3
Explanation:
The valid subsequences that sum up to 2 are:

• [1, 1]
• [2]
• [1, 1] (from different indices than the first one)

So the total number of valid subsequences is 3.

Approach:

We need to explore all subsequences and count only those whose sum is equal to K.

We’ll use the Pick / Not Pick recursion pattern to explore every combination.

• Base Case:
  If index ≥ length of array:

  • If current sum == target → return 1 (valid subsequence)
  • Else → return 0

• Recursive Steps:

  • Pick the element → add to current sum
  • Not Pick → skip it (sum remains same)

• Final Answer: Return the sum of both recursive calls

Recursive Tree Visualization:

Let’s say:

• arr = [1, 2, 1]
• target = 2

Here’s how the recursive calls branch out:

                    index=0, sum=0
                     /         \
               pick 1         not pick
               /                 \
      index=1, sum=1         index=1, sum=0
         /     \                 /      \
   pick 2   not pick      pick 2    not pick
     |         |             |          |
index=2,sum=3 1       index=2,sum=2 0
             ... and so on

Valid Subsequences Where Sum == 2:

• [1, 1]
• [2]
• [1, 1] (from different indices)

Total Count: 3

Code:

static int countSubSeq(int[] arr, int index, int target, int sum) {
    if (index >= arr.length) {
        if (sum == target) {
            return 1;
        }
        return 0;
    }

    int curr = arr[index];

    // Pick the current element
    int left = countSubSeq(arr, index + 1, target, sum + curr);

    // Do not pick the current element
    int right = countSubSeq(arr, index + 1, target, sum);

    return left + right;
}

---

Q 4. Check if there exists a subsequence with sum K:

Given an array and a target sum K.
Our task is to check whether at least one subsequence exists in the array whose elements sum up to K.

This is a Yes/No type problem — we just want to find one valid path, not count all.

Example:

Input: arr = [1, 2, 3], target = 5
Output: true
Explanation: The subsequence [2, 3] has a sum of 5.
We are not required to return the actual subsequence — just whether it exists.

Approach: Recursion – Pick / Not Pick

At each index, we have 2 choices:

• Pick the current element → reduce the target by arr[index]
• Don’t pick the current element → move to the next index with the same target

We recursively check both paths.
As soon as we find one path where the sum becomes 0, we return true.

Base Case:

if(index == arr.length){
    return target == 0;
}

If we reach the end of the array:

• If target == 0, a valid subsequence exists → return true
• Else → return false

Recursive Tree Visualization:

Let's say: arr = [1, 2, 3], target = 3

                      (0, 3)
                    /       \
              (1, 2)        (1, 3)
             /     \        /     \
         (2, 0)  (2, 2)  (2, 1)  (2, 3)
          /         ...     ...     ...
       return T

As soon as (2, 0) is reached, we return true because target == 0.

We stop exploring further once we find one valid path.

Code:

static boolean checkSubseq(int[] arr, int index, int target){
    if(index == arr.length){
        return target == 0;
    }

    int curr = arr[index];

    // Pick
    if(checkSubseq(arr, index + 1, target - curr)){
        return true;
    }

    // Not Pick
    if(checkSubseq(arr, index + 1, target)){
        return true;
    }

    return false;
}

---

Q 5. Subset Sum:

Given an array of integers, we need to find the sum of all subsequences and return them in a list.
This includes sums of all possible combinations (including empty subsequence).

Example:

Input: arr = [3, 1, 2]
Output: [6, 4, 5, 3, 3, 1, 2, 0]

Explanation:

All possible subsequences and their corresponding sums:

• [3, 1, 2] → 6
• [3, 1] → 4
• [3, 2] → 5
• [3] → 3
• [1, 2] → 3
• [1] → 1
• [2] → 2
• [] → 0

So, all subset sums = [6, 4, 5, 3, 3, 1, 2, 0] (order may vary depending on recursion path).

Approach (Pick / Not Pick):

We use recursion to explore all possible combinations by either:

1. Picking the current element → add it to sum
2. Not picking the current element → keep sum as is

We recursively go through each index, and when we reach the end of the array, we store the current sum in a result list.

Recursive Tree Visualization:

Input: arr = [3, 1, 2]

                                      (sum = 0)
                                     /         \
                            (sum = 3)           (sum = 0)
                            /       \           /       \
                   (sum = 4)     (sum = 3)   (sum = 1)   (sum = 0)
                   /     \       /     \     /     \     /     \
          (sum = 6) (sum = 4) (sum = 5) (sum = 3) (sum = 3)(sum = 1)(sum = 2)(sum = 0)

Sums:
→ 6 = (3+1+2)
→ 4 = (3+1)
→ 5 = (3+2)
→ 3 = (3)
→ 3 = (1+2)
→ 1 = (1)
→ 2 = (2)
→ 0 = (empty subset)

This shows how at each step, the function either includes the current element (sum + arr[i]) or excludes it (keeps sum the same).

Code:

static void subsetSum(int[] arr, int index, int sum, ArrayList<Integer> list) {
    if (index == arr.length) {
        list.add(sum);
        return;
    }

    int curr = arr[index];

    // Pick the current element
    subsetSum(arr, index + 1, sum + curr, list);

    // Not pick the current element
    subsetSum(arr, index + 1, sum, list);
}

---

What's next:

I’m continuing this journey and will be:

• Posting blogs every 3 days.
• Also learning Web Development — check out my Web Dev Journey Blog.
• You can follow my journey on X (Twitter) where I post regular updates.

---

Conclusion:

In this blog, we explored five powerful problems based on the concept of subsequences using recursion. Starting from printing all subsequences of an array or string, we moved step-by-step into more logic-heavy challenges like counting subsequences with a specific sum, checking if such a subsequence exists, and finally, finding all possible subset sums.

🔁 What ties them all together is the classic "pick or not pick" recursion pattern — a fundamental technique in solving many DSA problems. Understanding this recursive tree approach not only builds a strong base in recursion but also prepares me for dynamic programming problems ahead.

Keep practicing and visualizing the recursion tree — it makes complex logic much more intuitive!

If you're also starting your DSA journey, I hope this blog helps you understand recursion better. Keep learning and keep coding!

If you're on a similar journey, feel free to reach out or follow along — we’re all in this together.