☕ DSA Java Articles

Topics › Recursion and Backtracking › Subsequences Pattern

Check if there exists a subsequence with sum K

Easy TUF ID 879 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array nums of n integers and an integer k. Decide whether some subsequence of nums has elements adding up to exactly k, and return true or false.

A subsequence is obtained by deleting zero or more elements without reordering the rest, so each index is independently kept or dropped and there are 2^n candidates. The empty subsequence has sum 0; with k = 0 the answer is therefore true for every array. Values may be negative.

This is the “does any subsequence satisfy P” member of the subsequence pattern family. Compared with counting, the only change is that we are allowed to stop the moment a single success is found, and that small change is the whole point of the exercise.

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

Example 1

nums = [1, 2, 3], k = 5
answer = true            // 2 + 3

Example 2

nums = [1, 2, 3], k = 7
answer = false           // the largest possible sum is 1 + 2 + 3 = 6

Example 3

nums = [-5, 3, 8], k = -2
answer = true            // -5 + 3

Approach 1: Brute force, enumerate every subsequence

Intuition. Name each subsequence by an n-bit mask (bit i set means index i is kept), sum the chosen elements, and return true the first time a sum equals k. It is correct by definition and simple to write, but every mask is summed from scratch, so each candidate costs O(n) even though consecutive masks differ in very few positions.

Algorithm.

  1. For every mask from 0 to 2^n - 1:
  2. Add up nums[i] for every set bit i.
  3. If the sum equals k, return true.
  4. After the loop, return false.
static boolean bruteForce(int[] nums, int k) {
    int n = nums.length;
    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) return true;
    }
    return false;
}

Complexity. Time O(2^n · n) in the worst case (the answer is false, or the only match is the last mask). Space O(1).

The running sum is a long: several values near 2 × 10^9 overflow int, and a wrapped sum could accidentally equal k.

Approach 2: Optimal, pick / not-pick with early exit

Intuition. Build the subsequence one decision at a time. At index i with target still to be collected, either take nums[i] (new sub-problem: nums[i+1..] with target - nums[i]) or skip it (nums[i+1..] with target). Some subsequence of nums[i..] sums to target exactly when at least one of the two sub-problems succeeds, so the recursion returns pick || notPick.

The important detail is how that || is evaluated. We make the pick call first and, if it returns true, return immediately without ever exploring the not-pick subtree. In the counting version both subtrees are always needed; here, as soon as one leaf succeeds, every frame on the stack returns true and the remaining tree is skipped. When a solution exists early in the search this is dramatically faster; when the answer is false nothing can be skipped and the full 2^n tree is visited.

Algorithm.

  1. existsRec(i, target) answers: does some subsequence of nums[i..n-1] sum to target?
  2. Base case i == n: return target == 0.
  3. If existsRec(i + 1, target - nums[i]) is true, return true.
  4. Otherwise return existsRec(i + 1, target). The top-level call is existsRec(0, k).
static boolean optimal(int[] nums, int k) {
    return existsRec(nums, 0, k);
}

static boolean existsRec(int[] nums, int i, long target) {
    if (i == nums.length) return target == 0;
    if (existsRec(nums, i + 1, target - nums[i])) return true;   // pick nums[i]; if that works we are done
    return existsRec(nums, i + 1, target);                        // otherwise try leaving nums[i] out
}

Dry run on nums = [1, 2, 3], k = 5. The pick branch is always tried first.

call (i, target) action
(0, 5) pick 1 → (1, 4)
(1, 4) pick 2 → (2, 2)
(2, 2) pick 3 → (3, -1): leaf, false; not pick → (3, 2): leaf, false; returns false
(1, 4) not pick 2 → (2, 4)
(2, 4) pick 3 → (3, 1): false; not pick → (3, 4): false; returns false
(0, 5) not pick 1 → (1, 5)
(1, 5) pick 2 → (2, 3)
(2, 3) pick 3 → (3, 0): leaf, true

The true propagates straight up: (2, 3), (1, 5) and (0, 5) each return without touching their not-pick branch. Of the 15 internal and leaf calls a full tree would make, only 11 were performed; on larger inputs with an early solution the saving is far bigger.

Complexity. Time O(2^n) in the worst case, each node doing O(1) work; often much less thanks to the early exit. Space O(n) for the recursion stack.

Pruning for non-negative arrays. If no value is negative, target only ever decreases, so if (target < 0) return false before the recursive calls cuts off whole subtrees. It is not in the method above because negative values are allowed: with nums = [-5, 3, 8] and k = -2 the very first call already has a negative target and the shortcut would answer false on the spot, yet {-5, 3} sums to -2. Check the input before adding the shortcut.

Approach 3: Memoising repeated states

Intuition. The outcome of existsRec(i, target) depends only on (i, target), not on the path that led there, and with repeated values many paths share states. Caching the boolean per state means every distinct state is solved once, which turns the exponential tree into a table whose size is the number of distinct (index, remaining target) pairs. For non-negative arrays that is at most n · (k + 1), the classic subset-sum DP table. Because targets may be negative here, each index gets a hash map rather than a fixed-size row.

Algorithm.

  1. Create n + 1 empty maps, one per index, from remaining target to result.
  2. In existsMemo(i, target): handle the base case; otherwise return the cached value if present.
  3. Compute pick || notPick recursively (still short-circuiting), store it, and return it.
static boolean memoized(int[] nums, int k) {
    List<Map<Long, Boolean>> memo = new ArrayList<>();
    for (int i = 0; i <= nums.length; i++) memo.add(new HashMap<>());
    return existsMemo(nums, 0, k, memo);
}

static boolean existsMemo(int[] nums, int i, long target, List<Map<Long, Boolean>> memo) {
    if (i == nums.length) return target == 0;
    Boolean cached = memo.get(i).get(target);
    if (cached != null) return cached;
    boolean result = existsMemo(nums, i + 1, target - nums[i], memo) || existsMemo(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 occur; O(n · k) for non-negative input, but potentially still exponential for widely spread distinct values, when the maps simply never hit. Space O(n · S) for the maps plus O(n) stack.

Edge cases and pitfalls