Solution Target Sum

Problem Statement

Given a set of positive numbers (non zero) and a target sum 'S'. Each number should be assigned either a '+' or '-' sign. We need to find out total ways to assign symbols to make the sum of numbers equal to target 'S'.

Example 1:

Input: {1, 1, 2, 3}, S=1
Output: 3
Explanation: The given set has '3' ways to make a sum of '1': {+1-1-2+3} & {-1+1-2+3} & {+1+1+2-3}

Example 2:

Input: {1, 2, 7, 1}, S=9
Output: 2
Explanation: The given set has '2' ways to make a sum of '9': {+1+2+7-1} & {-1+2+7+1}

Constraints:

1 <= num.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

Solution

This problem follows the 0/1 Knapsack pattern and can be converted into "Count of Subset Sum" . Let's dig into this.

We are asked to find two subsets of the given numbers whose difference is equal to the given target 'S'. Take the first example above. As we saw, one solution is {+1-1-2+3}. So, the two subsets we are asked to find are {1, 3} & {1, 2} because,

    (1 + 3) - (1 + 2 ) = 1

Now, let's say 'Sum(s1)' denotes the total sum of set 's1', and 'Sum(s2)' denotes the total sum of set 's2'. So the required equation is:

    Sum(s1) - Sum(s2) = S

This equation can be reduced to the subset sum problem. Let's assume that 'Sum(num)' denotes the total sum of all the numbers, therefore:

    Sum(s1) + Sum(s2) = Sum(num)

Let's add the above two equations:

    => Sum(s1) - Sum(s2) + Sum(s1) + Sum(s2) = S + Sum(num)
    => 2 * Sum(s1) =  S + Sum(num)
    => Sum(s1) = (S + Sum(num)) / 2

This essentially converts our problem to: "Find count of subsets of the given numbers whose sum is equal to",

    => (S + Sum(num)) / 2

Code

Let's take the dynamic programming code of "Count of Subset Sum" and extend it to solve this problem:

java

class Solution {

  public int findTargetSubsets(int[] num, int s) {
    int totalSum = 0;
    for (int n : num) {
      totalSum += n;
      if (n < 1) return -1; //invalid input, the problem expects only positive numbers
    }

    // if 's + totalSum' is odd, we can't find a subset with sum equal to '(s + totalSum) / 2'
    if (totalSum < s || (s + totalSum) % 2 == 1) return 0;

    return countSubsets(num, (s + totalSum) / 2);
  }

  // this function is exactly similar to what we have in 'Count of Subset Sum' problem.
  private int countSubsets(int[] num, int sum) {
    int n = num.length;
    int[][] dp = new int[n][sum + 1];

    // populate the sum=0 columns, as we will always have an empty set for zero sum
    for (int i = 0; i < n; i++) dp[i][0] = 1;

    // with only one number, we can form a subset only when the required sum is equal to the number
    for (int s = 1; s <= sum; s++) {
      dp[0][s] = (num[0] == s ? 1 : 0);
    }

    // process all subsets for all sums
    for (int i = 1; i < num.length; i++) {
      for (int s = 1; s <= sum; s++) {
        dp[i][s] = dp[i - 1][s];
        if (s >= num[i]) dp[i][s] += dp[i - 1][s - num[i]];
      }
    }

    // the bottom-right corner will have our answer.
    return dp[num.length - 1][sum];
  }

  public static void main(String[] args) {
    Solution ts = new Solution();
    int[] num = { 1, 1, 2, 3 };
    System.out.println(ts.findTargetSubsets(num, 1));
    num = new int[] { 1, 2, 7, 1 };
    System.out.println(ts.findTargetSubsets(num, 9));
  }
}

The above solution has time and space complexity of , where ‘N’ represents total numbers and ‘S’ is the desired sum.

We can further improve the solution to use only space.

Space Optimized Solution

Here is the code for the space-optimized solution, using only a single array:

java

class Solution {

  public int findTargetSubsets(int[] num, int s) {
    int totalSum = 0;
    for (int n : num) {
      totalSum += n;
      if (n < 1) return -1; //invalid input, the problem expects only positive numbers
    }

    // if 's + totalSum' is odd, we can't find a subset with sum equal to '(s + totalSum) / 2'
    if (totalSum < s || (s + totalSum) % 2 == 1) return 0;

    return countSubsets(num, (s + totalSum) / 2);
  }

  // this function is exactly similar to what we have in 'Count of Subset Sum' problem.
  private int countSubsets(int[] num, int sum) {
    int n = num.length;
    int[] dp = new int[sum + 1];
    dp[0] = 1;

    // with only one number, we can form a subset only when the required sum is equal to the number
    for (int s = 1; s <= sum; s++) {
      dp[s] = (num[0] == s ? 1 : 0);
    }

    // process all subsets for all sums
    for (int i = 1; i < num.length; i++) {
      for (int s = sum; s >= 0; s--) {
        if (s >= num[i]) dp[s] += dp[s - num[i]];
      }
    }

    return dp[sum];
  }

  public static void main(String[] args) {
    Solution ts = new Solution();
    int[] num = { 1, 1, 2, 3 };
    System.out.println(ts.findTargetSubsets(num, 1));
    num = new int[] { 1, 2, 7, 1 };
    System.out.println(ts.findTargetSubsets(num, 9));
  }
}

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Target Sum? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Target Sum** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Target Sum** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Target Sum**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Target Sum**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Count of Subset Sum Solution Unbounded Knapsack →