14.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 '+' and '-' before each integer in nums and then concatenate all the integers.

• For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".

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

Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-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

There are 5 ways to assign symbols to make the sum of nums be target 3.

Solution: (Recursion)

Trying both + and - for all values

class Solution
{
public:
    int count = 0;
    void countTar(vector<int> &nums, int target, int pos, int sum)
    {

        if (pos == nums.size())
        {
            if (sum == target)
            {
                count++;
            }
            return;
        }

        countTar(nums, target, pos+1, sum + nums[pos]);
        countTar(nums, target, pos+1, sum - nums[pos]);

        return;
    }

    int findTargetSumWays(vector<int> &nums, int t)
    {
        countTar(nums, t, 0, 0);
        return count;
    }
};

Time Complexity: O(2^n)

Solution: (Recursion + Memo)

class Solution
{
public:
    int countTar(vector<int> &nums, int target, int pos, int sum, vector<vector<int>> &dp)
    {

        if (pos == nums.size())
        {
            if (sum == target)
            {
                return 1;
            }
            return 0;
        }

        if (dp[pos][sum + 1000] != -1)
        {
            return dp[pos][sum + 1000];
        }

        int plus = countTar(nums, target, pos + 1, sum + nums[pos], dp);
        int sub = countTar(nums, target, pos + 1, sum - nums[pos], dp);

        dp[pos][sum + 1000] = plus + sub;

        return plus + sub;
    }

    int findTargetSumWays(vector<int> &nums, int t)
    {
        vector<vector<int>> dp(nums.size(), vector<int>(2001, -1));
        return countTar(nums, t, 0, 0, dp);
    }
};

Solution: (Dynamic Programming)

Similar to check if there is a subset with given sum Here we have to count the no of subset with target sum We can assume two subset S1 - S2 = target S1 + S2 = total array sum We can use this two equation to count the no of ways we can create a target sum

Edge Case:- Count all zeros as it can be added to both the subsets

class Solution
{
public:
    int countSubset(vector<int> nums, int target)
    {

        int n = nums.size();

        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));

        for (int i = 0; i <= n; i++)
        {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= n; i++)
        {
            int val = nums[i - 1];
            for (int j = 1; j <= target; j++)
            {
                if (val <= j)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - val];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n][target];
    }

    int findTargetSumWays(vector<int> &nums, int S)
    {

        vector<int> v;
        int sum = 0;
        int c0 = 0;

        for (int i = 0; i < nums.size(); i++)
        {
            
            if (nums[i] == 0)
            {
                c0++;
            }
            else{
                v.push_back(nums[i]);
                sum += nums[i];
            }
        }

        if (sum < S || (sum + S) % 2 == 1)
        {
            return 0;
        }

        int target = (sum + S) / 2;

        int c = countSubset(v, target);

        c = c * pow(2, c0);

        return c;
    }
};

Time Complexity: O(n * m)