☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Learn All Patterns of Subsequences (Theory)

Easy TUF ID 2400 A2Z

Java source ↗ Edit this article ↗

What this covers

A subsequence of an array is what remains after deleting zero or more elements without changing the order of the rest. [3, 2] is a subsequence of [3, 1, 2]; [2, 3] is not. Each element is either kept or deleted, so an array of n elements has exactly 2^n subsequences, including the empty one and the whole array.

Almost every recursion and backtracking problem in the sheet (subsets, combination sum, subset sum, later the “DP on subsequences” chapter) is one recursion dressed in different clothes: for each index, take the element or do not take it. This article shows that recursion once, then the four ways it is routinely reshaped:

  1. print all subsequences;
  2. print the subsequences that satisfy a condition (here: sum equals k);
  3. print only one such subsequence and stop;
  4. count them.

A fifth shape, the “pick the next index” loop, generates the same subsequences in a different order and is the natural fit for some later problems. All examples use a = [3, 1, 2], and every method in the Java file is checked against a non-recursive bit-mask enumeration.

Pattern 1: Print all subsequences (take / not-take)

Walk an index through the array. At each index there are two choices: put a[index] into the current subsequence and move on, or move on without it. When the index reaches n, a decision has been made for every element, and the current list is one complete subsequence.

static List<List<Integer>> allSubsequences(int[] a) {
    List<List<Integer>> result = new ArrayList<>();
    collectAll(a, 0, new ArrayList<>(), result);
    return result;
}

static void collectAll(int[] a, int index, List<Integer> current, List<List<Integer>> result) {
    if (index == a.length) {                                   // base case: every index has been decided
        result.add(new ArrayList<>(current));                  // copy: current keeps changing after we return
        return;
    }
    current.add(a[index]);                                     // take a[index]
    collectAll(a, index + 1, current, result);
    current.remove(current.size() - 1);                        // undo, so the other branch sees the same prefix
    collectAll(a, index + 1, current, result);                 // not take
}

The recursion tree for [3, 1, 2] (left child = take, right child = not take):

[]                            index 0
├── [3]                       take 3
│   ├── [3, 1]                take 1
│   │   ├── [3, 1, 2] ✓
│   │   └── [3, 1]    ✓
│   └── [3]                   not take 1
│       ├── [3, 2]    ✓
│       └── [3]       ✓
└── []                        not take 3
    ├── [1]
    │   ├── [1, 2]    ✓
    │   └── [1]       ✓
    └── []
        ├── [2]       ✓
        └── []        ✓

Three facts about this code carry over to every variant:

Time O(2^n · n): 2^n leaves and a copy of up to n elements at each. Space O(n) for the recursion depth and the shared list.

Pattern 2: Subsequences with a given sum

To keep only subsequences whose elements add up to k, carry the running sum down as a parameter and check it at the leaf. Nothing else changes.

static List<List<Integer>> subsequencesWithSum(int[] a, int k) {
    List<List<Integer>> result = new ArrayList<>();
    collectWithSum(a, 0, 0, k, new ArrayList<>(), result);
    return result;
}

static void collectWithSum(int[] a, int index, long sum, int k, List<Integer> current, List<List<Integer>> result) {
    if (index == a.length) {
        if (sum == k) result.add(new ArrayList<>(current));   // only leaves with the right sum are answers
        return;
    }
    current.add(a[index]);
    collectWithSum(a, index + 1, sum + a[index], k, current, result);
    current.remove(current.size() - 1);
    collectWithSum(a, index + 1, sum, k, current, result);
}

For [3, 1, 2] and k = 3 the leaves that pass are [3] and [1, 2], in that order. The sum is a long so that arrays of large values cannot overflow it.

Carrying the sum as a parameter rather than recomputing it from current at the leaf keeps the leaf test O(1). The same idea works for any property that can be updated incrementally: product, count of odd elements, length.

If the elements are all non-negative, you can prune: when sum > k, no extension can bring it back down, so return early. With negative numbers that pruning is wrong, which is why the code shown does not do it.

Pattern 3: Print any one subsequence and stop

Problems often ask for a solution rather than all of them. Exploring the whole tree and then taking the first result works but wastes time. The standard technique is to make the recursion return a boolean meaning “found one”, and to stop exploring as soon as a branch reports success.

static Optional<List<Integer>> anyOneWithSum(int[] a, int k) {
    List<Integer> current = new ArrayList<>();
    if (findOne(a, 0, 0, k, current)) return Optional.of(current);
    return Optional.empty();
}

static boolean findOne(int[] a, int index, long sum, int k, List<Integer> current) {
    if (index == a.length) return sum == k;                   // base case: report whether this leaf is an answer
    current.add(a[index]);
    if (findOne(a, index + 1, sum + a[index], k, current)) return true;   // found on the take branch: keep current as it is
    current.remove(current.size() - 1);
    return findOne(a, index + 1, sum, k, current);            // otherwise the answer, if any, is on the not-take branch
}

The structure of findOne is the structure of collectWithSum with one change: each recursive call’s result is inspected. If the take branch returns true, we return true immediately without undoing the take, so current still holds the found subsequence when control gets back to the caller. Only if the take branch fails do we undo and try the not-take branch, whose result becomes ours.

For [3, 1, 2] and k = 3 the first leaf with sum 3 in take-first order is [3], and the branches under “take 3, take 1” are explored and abandoned before it is found. The method returns an Optional so that “no subsequence has this sum” and “the empty subsequence is the answer” (for k = 0) stay distinguishable.

A tempting alternative is a void function with a shared found flag that every frame checks. It works, but the boolean return is cleaner and composes: the caller learns the outcome directly from the call.

Pattern 4: Count the subsequences

When only the number of valid subsequences is needed, the recursion returns an int: a leaf returns 1 if it satisfies the condition and 0 otherwise, and every inner frame returns the sum of its two branches. No list is built at all.

static int countWithSum(int[] a, int k) {
    return count(a, 0, 0, k);
}

static int count(int[] a, int index, long sum, int k) {
    if (index == a.length) return sum == k ? 1 : 0;
    int take = count(a, index + 1, sum + a[index], k);
    int notTake = count(a, index + 1, sum, k);
    return take + notTake;
}

count([3, 1, 2], 0, 0, 3) is 2: the take-3 subtree contributes 1 (the leaf [3]) and the not-take-3 subtree contributes 1 ([1, 2]). For 1 .. 12 and k = 20 the answer is 45, which the tests cross-check against the length of the list from Pattern 2.

This is the shape that becomes dynamic programming later. The frame’s answer depends only on (index, sum), so the same pair reached by different paths gives the same count; memoising on (index, sum) turns the 2^n recursion into O(n · k). That is exactly the “subset sum equals target” DP.

Pattern 5: The pick-next-index loop

There is a second way to generate the same 2^n subsequences. Instead of deciding “in or out” for one fixed index, each frame chooses which element comes next from the indices at or after start, then recurses from just after it. Every frame records the current list on entry, because every node of this tree, not only the leaves, is a subsequence.

static List<List<Integer>> allSubsequencesPickLoop(int[] a) {
    List<List<Integer>> result = new ArrayList<>();
    pickLoop(a, 0, new ArrayList<>(), result);
    return result;
}

static void pickLoop(int[] a, int start, List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));                      // record on entry, not only at a leaf
    for (int i = start; i < a.length; i++) {
        current.add(a[i]);                                     // a[i] is the next element of the subsequence
        pickLoop(a, i + 1, current, result);                   // later elements must come from after i
        current.remove(current.size() - 1);
    }
}

For [3, 1, 2] the order is [], [3], [3, 1], [3, 1, 2], [3, 2], [1], [1, 2], [2]: subsequences grouped by their first element, then by their second, like words in a dictionary. The tree has 2^n nodes in total and depth at most n.

Why have two shapes for the same output? When the array is sorted and contains duplicates, the loop form makes “skip an element equal to the previous one at this level” a one-line check, which is how Subsets II and Combination Sum II avoid duplicate answers. The take / not-take form is more natural when there is exactly one decision per index and the problem later becomes DP.

A non-recursive cross-check: bit masks

An n-bit number encodes one subsequence: bit i set means a[i] is taken. Counting from 0 to 2^n - 1 enumerates them all without recursion.

static List<List<Integer>> allSubsequencesBitmask(int[] a) {
    List<List<Integer>> result = new ArrayList<>();
    for (int mask = 0; mask < (1 << a.length); mask++) {
        List<Integer> subsequence = new ArrayList<>();
        for (int i = 0; i < a.length; i++) {
            if ((mask & (1 << i)) != 0) subsequence.add(a[i]);
        }
        result.add(subsequence);
    }
    return result;
}

The order is by mask value: [], [3], [1], [3, 1], [2], [3, 2], [1, 2], [3, 1, 2]. The test suite sorts the outputs of Patterns 1 and 5 and of this method and requires them to be identical, which is a cheap way to catch a missing undo or a wrong base case.

Complexity, limits and pitfalls