10-line java dp solution, beat 95%


  • 0
    A
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for(int num : nums) sum += num;
        if(((S^sum)&1)==1 || sum<S || -sum>S) return 0;
        int target = (S+sum)>>>1;
        int[] dp = new int[target+1]; dp[0] = 1;
        for(int num : nums)
            for(int i=target; i>=num; i--)
                if(dp[i-num]>0) dp[i]+=dp[i-num];
        return dp[target];
    }

Log in to reply
 

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