C++: Target Sum

Thought Process

The problem requires finding the number of ways to assign '+' and '-' signs to elements of an array such that their sum equals the target. We transform the problem into finding a subset of numbers whose sum is (target + totalSum) / 2. This reduces the problem to a subset sum problem, which we solve using dynamic programming. We create a 2D array 't' where t[i][j] represents the number of ways to achieve sum 'j' using the first 'i' elements. Special handling is done for zeros, as they can be included in either subset without affecting the sum. 

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        
        // Basically, s1-s2 = target
        // We know    s1+s2 = sum
        // Therefore, s1 = (target+sum)/2

        // Now, problem reduces to find a subset whose sum = s1
        int n = nums.size();
        int sum = 0;
        int zeros = 0;

        for(int i=0;i<n;i++)
            sum += nums[i];

        int targetSum = (target+sum)/2;

        // When targetSum is not attainable.
        if((target+sum)%2==1 || abs(target)>sum)
            return 0;

        int t[n+1][targetSum+1];
        
        // If number of elements are zero, then we can't create targetSum
        for(int i=0;i<=targetSum;i++)
            t[0][i] = 0;

        // If targetSum = 0 then we can create an empty subset whose sum = 0.
        t[0][0]=1;
        for(int i=1;i<=n;i++){

            if(nums[i-1]==0)
                zeros++;

            // Zero can go to either subset: s1 & s2. Hence, two ways for each
            // zero. It can be part of s1 or it can be part of s2.
            t[i][0] = pow(2,zeros);
        }   

        for(int i=1;i<=n;i++){
            for(int j=1;j<=targetSum;j++){

                if(nums[i-1] > j)
                    t[i][j] = t[i-1][j];
                else // Case-1 reject it; Case-2 select it.
                    t[i][j] = t[i-1][j] + t[i-1][j-nums[i-1]];
            }
        }
        return t[n][targetSum];
    }
};

Code Complexity

Time Complexity: O(n * targetSum)

The algorithm iterates through each element and each possible sum value, resulting in a time complexity of O(n * targetSum), where n is the number of elements and targetSum is derived from the target.

Space Complexity: O(n * targetSum)

The algorithm uses a 2D array of size (n+1) x (targetSum+1) to store intermediate results.

Code copied!