algoadvance

Leetcode 494. Target Sum

Problem Statement

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.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.

Example 2:

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

Constraints:

Clarifying Questions

  1. Are there any constraints on memory usage?
    • No, typical constraints for a problem of this nature apply.
  2. Will the arrays always be non-empty?
    • Yes, nums.length is guaranteed to be at least 1.
  3. Can nums contain zeros?
    • Yes, nums can contain zeros.

Strategy

The problem is essentially to find the number of ways to assign + and - signs to the elements of the array so that their sum equals the target. This is a variation of the subset sum problem and can be approached using dynamic programming.

Here’s a concise step-by-step plan:

  1. Transformation: Convert the problem into a subset sum problem.
    • Let P be the subset of elements that are given the + sign.
    • Let N be the subset of elements that are given the - sign.
    • We need to find subsets such that sum(P) - sum(N) = target.

    Rearranging, we get:

    sum(P) = (target + sum(nums)) / 2

    This essentially transforms the problem into finding a subset with a sum of (target + sum(nums)) / 2.

  2. Check Feasibility:
    • If (target + sum(nums)) is odd, return 0 since it’s not possible to partition the sum into integers.
  3. Dynamic Programming:
    • Define a dp array where dp[i] represents the number of ways to achieve sum i.
    • Initialize dp[0] to 1 since there is one way to achieve the sum 0: use no elements.
    • Iterate over the elements in nums and update the dp array.

Code

#include <vector>
#include <numeric> // for std::accumulate

class Solution {
public:
    int findTargetSumWays(std::vector<int>& nums, int target) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        
        // If target + sum is not even, return 0 because (sumP) will not be an integer
        if ((sum + target) % 2 != 0) return 0;
        
        int subsetSum = (sum + target) / 2;

        if(subsetSum < 0) return 0; // Negative subset sum is not feasible

        std::vector<int> dp(subsetSum + 1, 0);
        dp[0] = 1; // There's one way to get to sum 0: pick nothing
        
        for (int num : nums) {
            for (int j = subsetSum; j >= num; --j) {
                dp[j] += dp[j - num];
            }
        }

        return dp[subsetSum];
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI