MediumSubsets

Target Sum

Explanation & Solution

Description

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols + and - before each integer in nums and then concatenate all the integers.

Return the number of different expressions that you can build, which evaluates to target.

Input: nums = [1,1,1,1,1], target = 3

Output: 5

Explanation: There are 5 ways to assign symbols to make the sum equal 3:

-1 + 1 + 1 + 1 + 1 = 3

+1 - 1 + 1 + 1 + 1 = 3

+1 + 1 - 1 + 1 + 1 = 3

+1 + 1 + 1 - 1 + 1 = 3

+1 + 1 + 1 + 1 - 1 = 3

Constraints

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

Approach

Subsets pattern

1. Transform into a Subset Sum Problem

Let P be the set of numbers assigned + and N be the set assigned -.
We need: sum(P) - sum(N) = target
Since sum(P) + sum(N) = totalSum, we get: sum(P) = (totalSum + target) / 2
The problem reduces to: count subsets of nums that sum to (totalSum + target) / 2.

2. Check Feasibility

If (totalSum + target) is odd, no valid split exists — return 0.
If |target| > totalSum, no combination of signs can reach the target — return 0.

3. DP Array Setup

Create a 1D DP array dp of size subsetSum + 1, initialized to 0.
Set dp[0] = 1 — there is exactly one way to form sum 0 (choose nothing).

4. Fill the DP Table

For each number in nums, iterate the DP array from right to left.
For each capacity j >= nums[i]: dp[j] += dp[j - nums[i]].
Iterating right-to-left ensures each number is used at most once.

5. Return the Result

dp[subsetSum] contains the count of subsets that sum to the target subset sum.
This equals the number of valid sign assignments.

Key Insight

The key mathematical insight is transforming the +/- sign assignment into a subset sum counting problem.
Using 1D DP with right-to-left traversal gives an efficient O(n * subsetSum) solution.

Time

O(n * subsetSum) where subsetSum = (totalSum + target) / 2.

Space

O(subsetSum) for the DP array.

Visualization

Input:

[1, 1, 1, 1, 1], target = 3

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Partition to K Equal Sum Subsets

Power Set with Bit Manipulation