DSA problem
Target Sum
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 + or - before each integer in nums and then concatenating all the integers. Return the number of different expressions that you can build, which evaluates to target.
A naive recursive search tries both + and - for each element and counts the leaves whose running sum equals target. That tree has 2^n paths, so direct enumeration is exponential and intractable beyond about 20 elements. Memoization on (index, current_sum) brings it down to polynomial, but a cleaner formulation removes the search entirely.
Split nums into two disjoint subsets P (elements assigned +) and N (elements assigned -). Then the expression evaluates to sum(P) - sum(N) = target, and we also have sum(P) + sum(N) = sum(nums). Adding those equations gives sum(P) = (sum(nums) + target) / 2. So the original problem reduces to: count the number of subsets of nums whose sum equals this derived value P.
This is a classic 0/1 knapsack counting problem. If (sum + target) is negative or odd, the answer is 0. Otherwise we run a 1D DP where dp[s] is the number of subsets that sum to s. We initialize dp[0] = 1 (one way to get sum 0: the empty subset) and for each num iterate the capacity dimension from P down to num so each element is used at most once. The final answer is dp[P], computed in O(n * P) time using O(P) space.
Examples
nums = [1,1,1,1,1], target = 35nums = [1], target = 11nums = [1,2,1], target = 02Constraints
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.