☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Subset sum equals to target

Hard TUF ID 323 SDE

Java source ↗ Edit this article ↗

Problem

You are given an array arr of n non-negative integers and a non-negative integer target. Decide whether some subset of the elements (any selection of positions, each used at most once, not necessarily contiguous) has a sum of exactly target. Return true or false.

Typical constraints (Coding Ninjas “Subset Sum Equal To K”): 1 ≤ n ≤ 1000, 0 ≤ target ≤ 1000, 0 ≤ arr[i] ≤ 10^9. The table-based solutions run in O(n × target), so the size of target is what matters, not the size of the elements.

Example 1

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

Example 2

arr = [2, 5, 1, 6, 7], target = 4
answer = false       // no selection of these numbers adds up to 4

Thinking in terms of choices

A subset is a sequence of n yes/no decisions, one per element. Walk over the elements from the last to the first, and keep track of how much of the target is still missing. At element i with remainder t:

The answer is true if either branch is true. Let canMake(i, t) mean “some subset of arr[0..i] sums to t”:

canMake(i, 0)  = true                   // the empty subset
canMake(-1, t) = false   for t > 0      // no elements left
canMake(i, t)  = canMake(i - 1, t)  OR  ( arr[i] ≤ t  AND  canMake(i - 1, t - arr[i]) )
answer         = canMake(n - 1, target)

Unlike the coin problems, taking arr[i] moves us to i - 1, not back to i. That single difference is what makes this a 0/1 problem: every element is used at most once.

Approach 1: Recursion

Intuition. Code the recurrence directly. Checking t == 0 first means we stop as soon as the target is met, even if elements remain; the rest are simply not chosen. Short-circuiting on the skip branch avoids exploring the take branch when the answer is already known.

Algorithm.

  1. If t == 0, return true.
  2. If i < 0, return false.
  3. Return canMake(i - 1, t) or (arr[i] ≤ t and canMake(i - 1, t - arr[i])).
static boolean recursion(int[] arr, int target) {
    return canMake(arr.length - 1, target, arr);
}

static boolean canMake(int i, int t, int[] arr) {
    if (t == 0) return true;                                   // the subset chosen so far already works
    if (i < 0) return false;                                   // no elements left, t still positive
    if (canMake(i - 1, t, arr)) return true;                   // skip arr[i]
    return arr[i] <= t && canMake(i - 1, t - arr[i], arr);     // take arr[i]
}

Complexity. Time O(2^n): in the worst case (no subset works) every one of the 2^n subsets is explored. Space O(n) for the recursion stack.

Approach 2: Memoization

Intuition. The state is just (i, t), with 0 ≤ i < n and 0 ≤ t ≤ target, so there are at most n × (target + 1) distinct calls. Many different subsets of the later elements leave the same remainder: in [1, 2, 3, ...], taking {3} and taking {1, 2} both reduce t by 3. Caching each state means it is answered once. An int table with three values (unknown, false, true) does the job; a Boolean[][] with null for unknown also works but boxes every entry.

Algorithm.

  1. Allocate dp[n][target + 1], all 0 (unknown).
  2. Run the recursion; if dp[i][t] is known, return it. Otherwise compute, store 2 for true or 1 for false, and return.
static boolean memoization(int[] arr, int target) {
    int[][] dp = new int[arr.length][target + 1];              // 0 = unknown, 1 = false, 2 = true
    return memo(arr.length - 1, target, arr, dp);
}

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

Complexity. Time O(n × target): each state does O(1) work. Space O(n × target) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. Index the table by “how many elements are allowed” instead of “which index is last”, so that the empty prefix has its own row. dp[i][t] means “some subset of the first i elements sums to t”. Row 0 (no elements) can only make t = 0. Each later row reads only the row above it, so fill top to bottom.

Algorithm.

  1. dp[i][0] = true for every i; dp[0][t] = false for t > 0.
  2. For i from 1 to n, with x = arr[i - 1], and t from 1 to target: dp[i][t] = dp[i - 1][t] || (x ≤ t && dp[i - 1][t - x]).
  3. Return dp[n][target].
static boolean tabulation(int[] arr, int target) {
    int n = arr.length;
    boolean[][] dp = new boolean[n + 1][target + 1];           // dp[i][t]: some subset of the first i elements sums to t
    for (int i = 0; i <= n; i++) dp[i][0] = true;              // the empty subset makes 0
    for (int i = 1; i <= n; i++) {
        int x = arr[i - 1];
        for (int t = 1; t <= target; t++) {
            dp[i][t] = dp[i - 1][t] || (x <= t && dp[i - 1][t - x]);
        }
    }
    return dp[n][target];
}

Dry run on Example 1 (arr = [1, 2, 3, 4], target = 4). T marks true:

first i elements t = 0 1 2 3 4
0 (none) T        
1 ({1}) T T      
2 ({1, 2}) T T T T  
3 ({1, 2, 3}) T T T T T
4 ({1, 2, 3, 4}) T T T T T

At row 3, t = 4 becomes true through “take 3, then dp[2][1] is true”, which is the subset {1, 3}.

Complexity. Time O(n × target). Space O(n × target).

Approach 4: Space optimised

Intuition. Row i reads only row i - 1, at column t and at a smaller column t - x. Keep one array can[] and update it in descending order of t. When we update can[t], the cell can[t - x] has not been touched yet in this pass, so it still describes the previous row, which means “without x”. That is exactly the 0/1 rule. In ascending order, can[t - x] might already include x, and we would be allowed to use x twice, turning the problem into the unbounded (coin) version.

Note also that can[t] only ever changes from false to true, so we only write when can[t - x] is true.

Algorithm.

  1. can[0] = true.
  2. For each element x, for t from target down to x: if can[t - x], set can[t] = true.
  3. Return can[target].
static boolean spaceOptimised(int[] arr, int target) {
    boolean[] can = new boolean[target + 1];                   // can[t]: t is a sum of a subset of the elements seen so far
    can[0] = true;
    for (int x : arr) {
        for (int t = target; t >= x; t--) {                    // descending: x is used at most once per subset
            if (can[t - x]) can[t] = true;
        }
    }
    return can[target];
}

Complexity. Time O(n × target). Space O(target). Elements larger than target are skipped automatically because the inner loop does not run.

Edge cases and pitfalls