AlgoDaily - Feature: Solving the Target Sum problem with dynamic programming and more

Mark As Completed Discussion

Home > Data Structures and Algorithms 🚀 > Hash Maps and Key Values > Feature: Solving the Target Sum problem with dynamic programming and more

number of ways to attain S without V is the value in the same column, but 1 row above, in our dynamic programming table.

number of ways to attain S-V with V is the value in the column V columns to the left, but 1 row above, in our dynamic programming table.

Therefore, in code, our final solution looks like this:

xxxxxxxxxx
}
 
class Main {
    public static int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num: nums) sum += num;
        if (S > sum || -S < -sum || (S + sum) % 2 == 1) return 0;
​
        int[] dp = new int[(S + sum) / 2 + 1];
        dp[0] = 1;
​
        for (int num: nums) {
            for (int i = dp.length - 1; i >= num; i--) {
                dp[i] += dp[i - num]; // Crux
            }
        }
​
        return dp[dp.length - 1];
    }
​
    public static void main(String[] args) {
        int[] nums = {
            8,
            7,
            1,
            5,
            3,
            8,
            11,
            6,
            14