Java: 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(int[] nums, int target) {
        
        int sum =0;
        int sz = nums.length;
        for(int i=0;i<nums.length;i++)
            sum += nums[i];
        
        int valSum = (target+sum)/2;
        if((target+sum)%2==1 || Math.abs(target) >sum)
            return 0;

        int[][] t = new int[sz+1][valSum+1];

        for(int i=0;i<=valSum;i++){
            t[0][i] = 0;
        }

        int cnt =0;
        for(int i=0;i<=sz;i++){

            if(i>0 && nums[i-1]==0)
                cnt++;

            t[i][0] = (int) Math.pow(2,cnt);
        }

        for(int i=1;i<=sz;i++){
            for(int j=1;j<=valSum;j++){

                if(nums[i-1]>j)
                    t[i][j] = t[i-1][j];
                else
                    t[i][j] = t[i-1][j] + t[i-1][j-nums[i-1]];
            }
        }
        return t[sz][valSum];
    }
}

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!