☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Subset sum equal to target (DP- 14)

Hard TUF ID 2804 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr of n positive integers and a target k. Return true if some subset of the elements (any selection, not necessarily contiguous, each element used at most once) adds up to exactly k, and false otherwise.

Typical constraints: 1 ≤ n ≤ 1000, 1 ≤ k ≤ 1000, and every arr[i] ≥ 1 (individual elements may be much larger than k). The DP below is O(n · k), so it relies on k being small; the size of the elements themselves does not matter. The Java methods also accept k = 0, which the empty subset always satisfies.

Example 1

arr = [1, 2, 3, 4], k = 4
answer = true        // {4} works, and so does {1, 3}

Example 2

arr = [2, 5, 1, 6, 7], k = 4
answer = false       // only 2 and 1 are below 4, and together they reach just 3

The pick / not-pick pattern

This is the first problem in the “DP on subsequences” family, and its recursion is the template for every problem after it. A subset is a sequence of independent decisions, one per element: either the element is in the subset or it is not. If we process the elements from the last index down to the first, a state needs only two numbers:

Picking arr[i] moves to (i - 1, t - arr[i]); skipping it moves to (i - 1, t). Everything already decided is summarised by t, which is exactly what makes the problem a DP: two different selections of the later elements that leave the same remainder t face the identical sub-problem.

Approach 1: Recursion

Intuition. Let f(i, t) answer: can some subset of arr[0..i] sum to t? Two base cases stop the recursion:

Otherwise the answer is “skip works, or take works”, and taking is only allowed when arr[i] ≤ t; because all elements are positive, a remainder can never go negative and come back.

f(i, 0) = true
f(0, t) = (arr[0] == t)
f(i, t) = f(i - 1, t)  OR  (arr[i] ≤ t AND f(i - 1, t - arr[i]))
answer  = f(n - 1, k)

Algorithm.

  1. If t == 0, return true. If i == 0, return arr[0] == t.
  2. Compute notTake = f(i - 1, t).
  3. Compute take = arr[i] ≤ t && f(i - 1, t - arr[i]).
  4. Return notTake || take.
static boolean recursive(int[] arr, int k) {
    return solve(arr.length - 1, k, arr);
}

static boolean solve(int i, int t, int[] arr) {
    if (t == 0) return true;                       // the empty subset already works
    if (i == 0) return arr[0] == t;                // one element left: take it or leave it
    boolean notTake = solve(i - 1, t, arr);
    boolean take = arr[i] <= t && solve(i - 1, t - arr[i], arr);
    return notTake || take;
}

Complexity. Time O(2^n): each element doubles the number of paths in the worst case. Space O(n) for the recursion depth.

Approach 2: Memoization

Intuition. The state is just (i, t) with 0 ≤ i < n and 0 ≤ t ≤ k, so there are at most n · (k + 1) distinct sub-problems while the recursion tree has up to 2^n nodes. With arr = [5, 1, 2, 3] and k = 6, taking only the 3, or skipping the 3 and taking 2 and 1 instead, both arrive at (0, 3): remainder 3 with only arr[0] left to decide. Caching each (i, t) once removes all such repetition.

A boolean cannot express “not computed yet”, so the table is an int[][] holding -1 (unknown), 0 (false) or 1 (true).

Algorithm.

  1. Create dp[n][k + 1] filled with -1.
  2. Run the same recursion; before computing (i, t), return the cached value if it exists; after computing it, store it.
static boolean memoization(int[] arr, int k) {
    int[][] dp = new int[arr.length][k + 1];       // -1 = unknown, 0 = false, 1 = true
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(arr.length - 1, k, arr, dp);
}

static boolean memo(int i, int t, int[] arr, int[][] dp) {
    if (t == 0) return true;
    if (i == 0) return arr[0] == t;
    if (dp[i][t] != -1) return dp[i][t] == 1;
    boolean notTake = memo(i - 1, t, arr, dp);
    boolean take = arr[i] <= t && memo(i - 1, t - arr[i], arr, dp);
    dp[i][t] = (notTake || take) ? 1 : 0;
    return notTake || take;
}

Complexity. Time O(n · k): each state is solved once in constant time. Space O(n · k) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. Turn the recursion inside out. dp[i][t] means the same thing as f(i, t), and row i depends only on row i - 1, so we fill rows from 0 upward. The base cases become initial values:

The second guard is easy to forget. An element larger than k cannot be part of any answer, but writing dp[0][arr[0]] = true without the check throws ArrayIndexOutOfBoundsException.

Algorithm.

  1. Set dp[i][0] = true for all i, and dp[0][arr[0]] = true if arr[0] ≤ k.
  2. For i from 1 to n - 1 and t from 1 to k: dp[i][t] = dp[i - 1][t] || (arr[i] ≤ t && dp[i - 1][t - arr[i]]).
  3. Return dp[n - 1][k].
static boolean tabulation(int[] arr, int k) {
    int n = arr.length;
    boolean[][] dp = new boolean[n][k + 1];
    for (int i = 0; i < n; i++) dp[i][0] = true;   // target 0: take nothing
    if (arr[0] <= k) dp[0][arr[0]] = true;         // row 0: only arr[0] itself is reachable
    for (int i = 1; i < n; i++) {
        for (int t = 1; t <= k; t++) {
            boolean notTake = dp[i - 1][t];
            boolean take = arr[i] <= t && dp[i - 1][t - arr[i]];
            dp[i][t] = notTake || take;
        }
    }
    return dp[n - 1][k];
}

Dry run on Example 1 (arr = [1, 2, 3, 4], k = 4), with T for true:

i (arr[i]) t = 0 1 2 3 4
0 (1) T T F F F
1 (2) T T T T F
2 (3) T T T T T
3 (4) T T T T T

Row 1 gains t = 3 by taking 2 on top of dp[0][1]. Row 2 reaches t = 4 by taking 3 on top of dp[1][1], which is the subset {1, 3}. The answer is dp[3][4] = true.

Complexity. Time O(n · k), space O(n · k).

Approach 4: Space optimized

Intuition. Row i reads only row i - 1. Keep that row as prev, build row i in a fresh array cur, then make cur the new prev. Remember to set cur[0] = true in every new row, since column 0 is a base case and a freshly allocated boolean[] starts all false.

(A single array updated from t = k down to t = 1 also works: going right to left, dp[t - arr[i]] still holds the previous row’s value when it is read. The two-array form is shown here because it maps line for line onto the tabulation.)

Algorithm.

  1. prev[0] = true, and prev[arr[0]] = true if arr[0] ≤ k.
  2. For each i from 1: build cur from prev with the same recurrence, then prev = cur.
  3. Return prev[k].
static boolean spaceOptimized(int[] arr, int k) {
    int n = arr.length;
    boolean[] prev = new boolean[k + 1];
    prev[0] = true;
    if (arr[0] <= k) prev[arr[0]] = true;
    for (int i = 1; i < n; i++) {
        boolean[] cur = new boolean[k + 1];
        cur[0] = true;
        for (int t = 1; t <= k; t++) {
            boolean notTake = prev[t];
            boolean take = arr[i] <= t && prev[t - arr[i]];
            cur[t] = notTake || take;
        }
        prev = cur;
    }
    return prev[k];
}

Complexity. Time O(n · k), space O(k).

Edge cases and pitfalls