How to write a two D solution


  • 0
    X

    public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
    int sum=0;
    for(int x: nums){
    sum+=x;
    }

        if(S>sum||(S+sum)%2==1) return 0;
        int tar=(S+sum)/2;
        
        int m=nums.length;
        int n=tar+1;
        
        int[][] dp=new int[m][n];
        for(int i=0; i<m; i++){
            dp[i][0]=1;
        }
       
        if(nums[0]<n) 
           dp[0][nums[0]]=1;
        //question? do not know why this is wrong
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(j-nums[i]>=0)
                   dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
                else
                   dp[i][j]=dp[i-1][j];
            }
        }
        
        return dp[m-1][n-1];
    

    }
    }

    I write this code with reference to 461 partition equal subset sum, but I do not know where does it goes wrong. For testcase [9,7,0,3,9,8,6,5,7,6] S=2, it generates an output of 37 instead of 40.


Log in to reply
 

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