Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Check if there exists a subsequence with sum K

EASYProblemSolveExternal Links

Description

Given an array of positive integers arr and a target sum k, determine whether there exists any subsequence (subset) of the array whose elements add up to exactly k.

A subsequence is formed by selecting zero or more elements from the array without changing their relative order. You do not need to pick consecutive elements. If at least one such subsequence exists whose sum equals k, return true. Otherwise, return false.

This is a decision problem — you only need to report whether such a subsequence exists, not identify which elements form it.

Examples

Example 1

Input: arr = [10, 1, 2, 7, 6, 1, 5], k = 8

Output: true

Explanation: Multiple subsequences sum to 8. For instance, the subsequence {1, 7} sums to 1 + 7 = 8. Another valid choice is {2, 6} which also sums to 2 + 6 = 8. Since at least one such subsequence exists, the answer is true.

Example 2

Input: arr = [2, 3, 5, 7, 9], k = 100

Output: false

Explanation: The total sum of all elements is 2 + 3 + 5 + 7 + 9 = 26, which is far less than 100. No matter which elements we select, we cannot reach a sum of 100. Therefore the answer is false.

Example 3

Input: arr = [4, 2, 1], k = 3

Output: true

Explanation: The subsequence {2, 1} sums to 2 + 1 = 3, which equals the target. Therefore the answer is true.

Constraints

  • 1 ≤ arr.length ≤ 2000
  • 1 ≤ arr[i] ≤ 1000
  • 1 ≤ k ≤ 2000

Editorial

Brute Force

Intuition

The most straightforward approach is to try every possible subsequence and check if any of them sums to k.

Imagine you are packing a bag and you have a list of items, each with a specific weight. You want to know if you can pick some items so their total weight is exactly a target value. The brute force way is to consider every possible combination of items: for each item, you either put it in the bag or leave it out, and then check the total.

We use recursion to model this decision process. At each element, we branch into two paths:

  • Include the current element (subtract its value from the remaining target)
  • Exclude the current element (keep the remaining target unchanged)

If at any point the remaining target becomes 0, we have found a valid subsequence. If we exhaust all elements without reaching 0, that particular path fails.

Step-by-Step Explanation

Let's trace through with arr = [2, 3, 5], k = 8.

We call solve(index=0, remaining=8) and explore the recursion tree:

Step 1: solve(0, 8) — Start at index 0, need sum = 8. We try including arr[0] = 2.

Step 2: solve(1, 6) — Included 2, remaining = 8 - 2 = 6. Try including arr[1] = 3.

Step 3: solve(2, 3) — Included 3, remaining = 6 - 3 = 3. Try including arr[2] = 5.

Step 4: solve(3, -2) — Included 5, remaining = 3 - 5 = -2. Negative remaining means we overshot. Return false.

Step 5: Backtrack to solve(2, 3). Try skipping arr[2] = 5.

Step 6: solve(3, 3) — Skipped 5, remaining = 3. Index = 3 = array length, but remaining ≠ 0. Return false.

Step 7: solve(2, 3) both branches returned false. Return false. solve(1, 6) now tries skipping arr[1] = 3.

Step 8: solve(2, 6) — Skipped 3, remaining = 6. Try including arr[2] = 5.

Step 9: solve(3, 1) — Included 5, remaining = 6 - 5 = 1. Index = 3, remaining ≠ 0. Return false.

Step 10: Backtrack. solve(2, 6) tries skipping arr[2] = 5.

Step 11: solve(3, 6) — All skipped after index 1, remaining = 6 ≠ 0. Return false.

Step 12: solve(2, 6) returns false. solve(1, 6) returns false. Back to solve(0, 8), try skipping arr[0] = 2.

Step 13: solve(1, 8) — Skipped 2, remaining = 8. Try including arr[1] = 3.

Step 14: solve(2, 5) — Included 3, remaining = 8 - 3 = 5. Try including arr[2] = 5.

Step 15: solve(3, 0) — Included 5, remaining = 5 - 5 = 0. Remaining is 0! Found a valid subsequence! Return true.

Step 16: Propagate true upward: solve(2,5) = true → solve(1,8) = true → solve(0,8) = true.

Result: true. The subsequence {3, 5} sums to 8.

Recursive Backtracking — Exploring All Subsequences — Watch the recursion tree expand as we try including/excluding each element. The algorithm backtracks when a path fails, until it finds a subsequence summing to the target.

Algorithm

  1. Define a recursive function solve(index, remaining) that returns true if a subsequence starting from index sums to remaining
  2. Base cases:
    • If remaining == 0, return true (found a valid subsequence)
    • If index == n or remaining < 0, return false (exhausted elements or overshot)
  3. Recursive case: return solve(index + 1, remaining - arr[index]) OR solve(index + 1, remaining)
    • First branch: include arr[index] (subtract from remaining)
    • Second branch: exclude arr[index] (remaining unchanged)
  4. Call solve(0, k) and return its result

Code

class Solution {
public:
    bool checkSubsequenceSum(int N, vector<int>& arr, int K) {
        return solve(arr, 0, K);
    }

private:
    bool solve(vector<int>& arr, int idx, int remaining) {
        if (remaining == 0) return true;
        if (idx == (int)arr.size() || remaining < 0) return false;

        // Include arr[idx] or skip it
        return solve(arr, idx + 1, remaining - arr[idx])
            || solve(arr, idx + 1, remaining);
    }
};
class Solution:
    def checkSubsequenceSum(self, N, arr, K):
        def solve(idx, remaining):
            if remaining == 0:
                return True
            if idx == N or remaining < 0:
                return False
            # Include arr[idx] or skip it
            return solve(idx + 1, remaining - arr[idx]) or \
                   solve(idx + 1, remaining)

        return solve(0, K)
class Solution {
    public boolean checkSubsequenceSum(int N, int[] arr, int K) {
        return solve(arr, 0, K);
    }

    private boolean solve(int[] arr, int idx, int remaining) {
        if (remaining == 0) return true;
        if (idx == arr.length || remaining < 0) return false;

        // Include arr[idx] or skip it
        return solve(arr, idx + 1, remaining - arr[idx])
            || solve(arr, idx + 1, remaining);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each element, the recursion branches into two paths (include or exclude). This creates a binary tree with up to 2^n leaf nodes. For n = 2000, 2^2000 is an incomprehensibly large number — the algorithm would never terminate in practice.

Space Complexity: O(n)

The maximum recursion depth equals the array length n, since each recursive call processes one element. Each stack frame uses O(1) space, so the call stack requires O(n) total space.

Why This Approach Is Not Efficient

The brute force explores 2^n paths, which is catastrophically slow. With n = 2000, even a computer performing 10^9 operations per second would need more time than the age of the universe.

The fundamental flaw is redundant computation: the recursion visits the same (index, remaining_sum) state multiple times through different paths. For instance, with arr = [3, 3, 3, ...], the call solve(5, 10) might be reached by including the first three 3's and skipping two, or by including the last three 3's and skipping two — same state, computed twice.

This is the signature of overlapping subproblems, which means Dynamic Programming can eliminate the redundancy. Instead of re-exploring a state we have already resolved, we can store (memoize) its result. The total number of unique states is at most N × K (index values 0..N, remaining values 0..K), so the DP approach runs in O(N × K) time — polynomial instead of exponential.

Better Approach - Dynamic Programming (2D Table)

Intuition

Instead of recursively branching and recomputing overlapping states, we build a table that answers the question bottom-up: "Using only the first i elements, can we form a subsequence with sum exactly j?"

We create a 2D boolean table dp[i][j] where:

  • Rows represent how many elements we have considered (0 to N)
  • Columns represent target sums (0 to K)
  • dp[i][j] = true means there exists a subsequence of the first i elements that sums to j

The base case is straightforward: dp[i][0] = true for all i, because the empty subsequence always achieves sum 0.

For each element arr[i-1] and each target sum j, we have two choices:

  • Skip the element: dp[i][j] = dp[i-1][j] (same achievability as without this element)
  • Include the element (if j ≥ arr[i-1]): dp[i][j] = dp[i-1][j - arr[i-1]] (we needed sum j - arr[i-1] before adding this element)

We take the OR of both choices. The final answer is dp[N][K].

Step-by-Step Explanation

Let's trace with arr = [2, 3, 5], k = 8.

We build a table dp[4][9] (rows 0-3, columns 0-8).

Step 1: Initialize base case: dp[0][0] = true (empty subsequence, sum 0). All dp[0][j] for j > 0 are false.
Row 0: [T, F, F, F, F, F, F, F, F]

Step 2: Row 1 — consider element arr[0] = 2.

  • dp[1][0] = true (skip element, empty subseq)
  • dp[1][1] = dp[0][1] = false (can't make sum 1 with just element 2)
  • dp[1][2] = dp[0][2] OR dp[0][0] = false OR true = true (include 2: sum 0 + 2 = 2)
  • dp[1][3..8] = false (can't exceed sum 2 with one element of value 2)
    Row 1: [T, F, T, F, F, F, F, F, F]

Step 3: Row 2 — add element arr[1] = 3.

  • dp[2][2] = dp[1][2] = true (carry over: sum 2 without using element 3)
  • dp[2][3] = dp[1][3] OR dp[1][0] = false OR true = true (include 3: 0 + 3 = 3)
  • dp[2][5] = dp[1][5] OR dp[1][2] = false OR true = true (include 3: 2 + 3 = 5)
    Row 2: [T, F, T, T, F, T, F, F, F]

Step 4: Row 3 — add element arr[2] = 5.

  • dp[3][5] = dp[2][5] OR dp[2][0] = true (already reachable)
  • dp[3][7] = dp[2][7] OR dp[2][2] = false OR true = true (include 5: 2 + 5 = 7)
  • dp[3][8] = dp[2][8] OR dp[2][3] = false OR true = true (include 5: 3 + 5 = 8) ← TARGET!
    Row 3: [T, F, T, T, F, T, F, T, T]

Result: dp[3][8] = true. The subsequence {3, 5} achieves sum 8.

2D DP Table — Building Reachable Sums Row by Row — Watch how each row builds on the previous row's results. A cell becomes true either by inheriting from above (skip element) or by looking back by the element's value (include element).

Algorithm

  1. Create a 2D boolean array dp of size (N + 1) × (K + 1), initialized to false
  2. Set dp[i][0] = true for all i from 0 to N (empty subsequence achieves sum 0)
  3. For each element i from 1 to N:
    • For each target sum j from 1 to K:
      • dp[i][j] = dp[i-1][j] (skip current element)
      • If j ≥ arr[i-1]: dp[i][j] = dp[i][j] OR dp[i-1][j - arr[i-1]] (include current element)
  4. Return dp[N][K]

Code

class Solution {
public:
    bool checkSubsequenceSum(int N, vector<int>& arr, int K) {
        vector<vector<bool>> dp(N + 1, vector<bool>(K + 1, false));

        // Base case: sum 0 is always achievable
        for (int i = 0; i <= N; i++)
            dp[i][0] = true;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                // Option 1: skip element arr[i-1]
                dp[i][j] = dp[i - 1][j];
                // Option 2: include element arr[i-1]
                if (j >= arr[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];
                }
            }
        }
        return dp[N][K];
    }
};
class Solution:
    def checkSubsequenceSum(self, N, arr, K):
        dp = [[False] * (K + 1) for _ in range(N + 1)]

        # Base case: sum 0 is always achievable
        for i in range(N + 1):
            dp[i][0] = True

        for i in range(1, N + 1):
            for j in range(1, K + 1):
                # Skip element
                dp[i][j] = dp[i - 1][j]
                # Include element if possible
                if j >= arr[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j - arr[i - 1]]

        return dp[N][K]
class Solution {
    public boolean checkSubsequenceSum(int N, int[] arr, int K) {
        boolean[][] dp = new boolean[N + 1][K + 1];

        // Base case: sum 0 is always achievable
        for (int i = 0; i <= N; i++)
            dp[i][0] = true;

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                // Skip element
                dp[i][j] = dp[i - 1][j];
                // Include element if possible
                if (j >= arr[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];
                }
            }
        }
        return dp[N][K];
    }
}

Complexity Analysis

Time Complexity: O(N × K)

We fill a table with (N + 1) rows and (K + 1) columns. Each cell is computed in O(1) time using the recurrence relation (one lookup for skip, one lookup for include, one OR operation). With N up to 2000 and K up to 2000, this is at most 4 million operations — very fast.

Space Complexity: O(N × K)

The 2D dp table stores (N + 1) × (K + 1) boolean values. For maximum constraints, that is 2001 × 2001 ≈ 4 million booleans, roughly 4 MB of memory.

Why This Approach Is Not Efficient

The 2D DP approach runs in O(N × K) time, which is efficient. However, it uses O(N × K) space — a 2D table that can reach 4 million entries for the maximum constraints.

The critical observation is that when filling row i, we only ever look at row i - 1. Rows i - 2, i - 3, etc., are never accessed again. This means we are storing an entire history of the table that is completely useless after processing the next element.

If we could reduce the table from 2D to 1D — maintaining just a single row and updating it in-place — we would cut the space from O(N × K) down to O(K). The trick is to iterate the sums in reverse order (from K down to arr[i]) when updating the 1D array. This prevents an element from being "used twice" in a single row update: by going right-to-left, each cell reads from values that haven't yet been updated in this iteration, effectively simulating the look-back to the previous row.

Optimal Approach - Space-Optimized Dynamic Programming

Intuition

We compress the 2D table into a single 1D array dp[0..K] where dp[j] means "can we form a subsequence from the elements processed so far that sums to exactly j?"

We start with dp[0] = true (empty subsequence) and everything else false. Then for each element in the array, we update the dp array by iterating sums from K down to the element's value:

dp[j] = dp[j] OR dp[j - arr[i]]

The reverse iteration is the key insight: if we iterated left-to-right, we might use the same element multiple times in one update (since dp[j - arr[i]] might have already been updated in this pass). By going right-to-left, dp[j - arr[i]] still reflects the state before the current element was added.

Think of it like updating a scoreboard: you read old scores from the left side to update new scores on the right. By processing right-to-left, you guarantee you are always reading last round's scores, not accidentally reading scores you just updated this round.

Step-by-Step Explanation

Let's trace with arr = [2, 3, 5], k = 8.

Step 1: Initialize dp = [T, F, F, F, F, F, F, F, F] (only sum 0 reachable).

Step 2: Process element 2 (iterate j from 8 down to 2):

  • j = 8: dp[8] OR dp[6] = F OR F = F
  • j = 7: dp[7] OR dp[5] = F OR F = F
  • j = 6 through 3: all remain F (dp[j-2] is F for all)
  • j = 2: dp[2] OR dp[0] = F OR T = T (include element 2: sum = 0 + 2 = 2)
    dp = [T, F, T, F, F, F, F, F, F]

Step 3: Process element 3 (iterate j from 8 down to 3):

  • j = 8 through 6: remain F
  • j = 5: dp[5] OR dp[2] = F OR T = T (include 3 with sum 2: 2 + 3 = 5)
  • j = 4: dp[4] OR dp[1] = F OR F = F
  • j = 3: dp[3] OR dp[0] = F OR T = T (include 3 alone: 0 + 3 = 3)
    dp = [T, F, T, T, F, T, F, F, F]

Step 4: Process element 5 (iterate j from 8 down to 5):

  • j = 8: dp[8] OR dp[3] = F OR T = T (include 5 with sum 3: 3 + 5 = 8) ← TARGET!
  • j = 7: dp[7] OR dp[2] = F OR T = T (include 5 with sum 2: 2 + 5 = 7)
  • j = 6: dp[6] OR dp[1] = F OR F = F
  • j = 5: dp[5] OR dp[0] = T OR T = T (already reachable)
    dp = [T, F, T, T, F, T, F, T, T]

Result: dp[8] = true. Subsequence {3, 5} sums to 8.

1D DP Array — Updating Reachable Sums In-Place — Watch the single dp array evolve as each element is processed. We iterate right-to-left to avoid using the same element twice. Cells flip from F to T as new sums become reachable.

Algorithm

  1. Create a 1D boolean array dp of size K + 1, initialized to false
  2. Set dp[0] = true (empty subsequence achieves sum 0)
  3. For each element arr[i] in the array:
    • For j from K down to arr[i] (reverse order is critical):
      • dp[j] = dp[j] OR dp[j - arr[i]]
  4. Return dp[K]

Code

class Solution {
public:
    bool checkSubsequenceSum(int N, vector<int>& arr, int K) {
        vector<bool> dp(K + 1, false);
        dp[0] = true;

        for (int i = 0; i < N; i++) {
            // Iterate in reverse to avoid using the same element twice
            for (int j = K; j >= arr[i]; j--) {
                dp[j] = dp[j] || dp[j - arr[i]];
            }
        }
        return dp[K];
    }
};
class Solution:
    def checkSubsequenceSum(self, N, arr, K):
        dp = [False] * (K + 1)
        dp[0] = True

        for num in arr:
            # Iterate in reverse to avoid using the same element twice
            for j in range(K, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]

        return dp[K]
class Solution {
    public boolean checkSubsequenceSum(int N, int[] arr, int K) {
        boolean[] dp = new boolean[K + 1];
        dp[0] = true;

        for (int i = 0; i < N; i++) {
            // Iterate in reverse to avoid using the same element twice
            for (int j = K; j >= arr[i]; j--) {
                dp[j] = dp[j] || dp[j - arr[i]];
            }
        }
        return dp[K];
    }
}

Complexity Analysis

Time Complexity: O(N × K)

For each of the N elements, we iterate through at most K sum values. Each iteration performs O(1) work (one array lookup and one OR). Total: N × K operations. For maximum constraints (N = 2000, K = 2000), this is 4 million operations — runs in milliseconds.

Space Complexity: O(K)

We maintain a single boolean array of size K + 1. For K = 2000, this is just 2001 booleans — roughly 2 KB of memory. This is a dramatic improvement over the 2D approach's O(N × K) ≈ 4 MB.

The key insight enabling this space reduction is that each row of the 2D DP table depends only on the immediately preceding row. By iterating sums in reverse and updating in-place, we effectively simulate the row-by-row computation with a single array.