Question on target sum


  • 0
    B

    Hi all,
    I have a question regarding the problem. I find when I remove "Arrays.sort()", my code won't work, but the logic seems correct. I hope somebody can help review my code and tell me if there's something wrong with my initialization. Thanks.

    public class Solution {
        public int findTargetSumWays(int[] A, int S) {
            
        	int sum = 0;
            for(int a:A)
            	sum += a;
            
            if(S>sum || (sum+S)%2==1)
            	return 0;
            
            sum = (sum+S)/2;
            
            Arrays.sort(A);
            
            int[][] dp = new int[A.length+1][sum+1];
            
            int zeros = 0;
            
            for(int i=0;i<A.length;i++){
                if(A[i]==0)
                    zeros++;
            }      
            
            for(int i=0;i<=A.length;i++)
            	dp[i][0] = 1;
            
            for(int i=1;i<=A.length;i++){
            	for(int j=1;j<=sum;j++){
            		dp[i][j] = j>=A[i-1] ? dp[i-1][j-A[i-1]]+ dp[i-1][j] : dp[i-1][j];
            	}
            }
            
            return dp[A.length][sum]*(int) (Math.pow(2, zeros));
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.