☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Count all subsequences with sum K

Easy TUF ID 880 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array nums of n integers and an integer k. Count how many subsequences of nums have elements that add up to exactly k.

A subsequence is what remains after deleting zero or more elements without changing the order of the rest. Equivalently, every index is either kept or dropped, so an array of n elements has exactly 2^n subsequences. Two subsequences that come from different index sets are counted separately even if they contain the same values: in [1, 2, 1] the two single 1s are two different subsequences. The empty subsequence has sum 0, so with k = 0 it is counted; if your judge wants it excluded, subtract one from the answer.

Constraints: 0 ≤ n ≤ 20 for the exponential approaches, values and k fit in a 32-bit signed integer, values may be negative.

Example 1

nums = [1, 2, 1], k = 2
answer = 2               // {1, 1} (indices 0 and 2) and {2}

Example 2

nums = [1, 2, 3, 4, 5], k = 5
answer = 3               // {5}, {1, 4}, {2, 3}

Example 3

nums = [1, 2, 3], k = 7
answer = 0               // the whole array only sums to 6

Approach 1: Brute force, enumerate every subsequence

Intuition. There are 2^n subsequences and a bitmask of n bits names each one: bit i set means “index i is kept”. Counting the masks 0 .. 2^n - 1, summing the chosen elements for each and comparing with k is the literal definition of the problem. It is slow because every mask is rebuilt from scratch, n work per mask, even though neighbouring masks share almost all of their elements.

Algorithm.

  1. For every mask from 0 to 2^n - 1:
  2. Add up nums[i] for every bit i that is set in mask.
  3. If the sum equals k, increment the counter.
  4. Return the counter.
static long bruteForce(int[] nums, int k) {
    int n = nums.length;
    long count = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        long sum = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) sum += nums[i];
        }
        if (sum == k) count++;
    }
    return count;
}

Complexity. Time O(2^n · n): 2^n masks, each summed in O(n). Space O(1): a counter and a running sum.

The sum is accumulated in a long. Twenty values near 2 × 10^9 add up to 4 × 10^10, far outside int, and a wrapped sum could accidentally equal k.

Approach 2: Optimal, pick / not-pick recursion that returns a count

Intuition. Instead of naming a subsequence by a finished mask, build it one decision at a time. Standing at index i with target still to be collected, there are two moves: take nums[i], which turns the problem into “subsequences of nums[i+1..] summing to target - nums[i]”, or leave it, which turns it into “subsequences of nums[i+1..] summing to target”. The two sub-problems describe disjoint sets of subsequences (one set contains index i, the other does not) and together they cover everything, so the answer is simply their sum. At the end of the array nothing is left to decide: the one subsequence we built is valid exactly when target has been reduced to 0.

This is the general “count the subsequences with property P” pattern from the subsequence theory lecture: the base case returns 1 or 0, and each internal node returns pick + notPick. The same skeleton with || instead of + answers the yes/no version, and with list building instead of counting it prints the subsequences.

Algorithm.

  1. countRec(i, target) answers: how many subsequences of nums[i..n-1] sum to target?
  2. Base case i == n: return 1 if target == 0, otherwise 0.
  3. pick = countRec(i + 1, target - nums[i]).
  4. notPick = countRec(i + 1, target).
  5. Return pick + notPick. The top-level call is countRec(0, k).
static long optimal(int[] nums, int k) {
    return countRec(nums, 0, k);
}

static long countRec(int[] nums, int i, long target) {
    if (i == nums.length) return target == 0 ? 1 : 0;
    long pick = countRec(nums, i + 1, target - nums[i]);
    long notPick = countRec(nums, i + 1, target);
    return pick + notPick;
}

Dry run on nums = [1, 2, 1], k = 2. Each row is one call; the leaves return 1 only when the remaining target is 0.

call (i, target) pick → notPick → returns
(0, 2) (1, 1) (1, 2) 1 + 1 = 2
(1, 1) (2, -1) → (3, -2)=0, (3, -1)=0 (2, 1) → (3, 0)=1, (3, 1)=0 0 + 1 = 1
(1, 2) (2, 0) → (3, -1)=0, (3, 0)=1 (2, 2) → (3, 1)=0, (3, 2)=0 1 + 0 = 1

The two leaves that return 1 correspond to picking indices 0, 2 (the two 1s) and picking index 1 alone (the 2).

Complexity. Time O(2^n): the recursion tree is a full binary tree of depth n, and each node does constant work, so the n factor of the brute force disappears. Space O(n) for the recursion stack.

Pruning when every value is non-negative. If no element is negative the running target can never go back up once it drops below 0, so if (target < 0) return 0 can be added before the recursive calls and whole subtrees vanish. The method above does not include it because the problem allows negative values: with nums = [-1, 1, 2, -2] and k = 0, the subsequence {2, -2} passes through target -2 before coming back to 0, and pruning would miss it. Add the shortcut only after checking the input.

Approach 3: Memoising the recursion

Intuition. Different paths can reach the same state (i, target): in [1, 1, 1, 1] the state “index 2, target 1” is reached both by picking the first element and by picking the second. The count for a state depends only on the state, not on how it was reached, so storing it after the first computation and reusing it afterwards turns the exponential tree into a table of distinct states. This is exactly the step from recursion to dynamic programming; the full tabulation is the subject of the DP problem linked below.

Because values may be negative, the remaining target is not confined to 0..k, so a plain 2D array indexed by target does not work. A list of hash maps, one per index, keyed by the remaining target, handles any range.

Algorithm.

  1. Create n + 1 empty maps memo[i] from remaining target to count.
  2. In countMemo(i, target): return the base case as before; otherwise look up memo[i].get(target) and return it if present.
  3. Compute pick + notPick recursively, store it in memo[i], and return it.
static long memoized(int[] nums, int k) {
    List<Map<Long, Long>> memo = new ArrayList<>();
    for (int i = 0; i <= nums.length; i++) memo.add(new HashMap<>());
    return countMemo(nums, 0, k, memo);
}

static long countMemo(int[] nums, int i, long target, List<Map<Long, Long>> memo) {
    if (i == nums.length) return target == 0 ? 1 : 0;
    Long cached = memo.get(i).get(target);
    if (cached != null) return cached;
    long result = countMemo(nums, i + 1, target - nums[i], memo) + countMemo(nums, i + 1, target, memo);
    memo.get(i).put(target, result);
    return result;
}

Complexity. Time O(n · S) where S is the number of distinct remaining targets that actually occur; for non-negative arrays S ≤ k + 1, so the running time is O(n · k). In the worst case (all distinct, widely spread values) S can still be exponential and memoisation buys nothing, which is why the plain recursion is the standard answer for this problem and the DP version is a separate one. Space O(n · S) for the maps plus O(n) stack.

Edge cases and pitfalls