Top 100
Target Sum
- Problem
- LC 494
- File
- top100_LC494TargetSum.java
- Path
- pkg5leetcode/top100/top100_LC494TargetSum.java
- Package
- pkg5leetcode.top100
- Command
- java pkg5leetcode/top100/top100_LC494TargetSum.java
- Approach
- DP count ways to reach each sum adding +/- each number.
- Complexity
- Time O(n*sum), Space O(sum)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.top100;2 3/*4 * Target Sum | LC 4945 * APPROACH: DP count ways to reach each sum adding +/- each number.6 * COMPLEXITY: Time O(n*sum), Space O(sum)7 */8public class top100_LC494TargetSum {9 static int findTargetSumWays(int[] nums, int target) {10 int sum = 0;11 for (int x : nums) sum += x;12 if ((target + sum) % 2 != 0 || target > sum) return 0;13 int need = (target + sum) / 2;14 int[] dp = new int[need + 1];15 dp[0] = 1;16 for (int x : nums) {17 for (int s = need; s >= x; s--) dp[s] += dp[s - x];18 }19 return dp[need];20 }21 22 public static void main(String[] args) {23 check(findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3) == 5, "case1");24 check(findTargetSumWays(new int[]{1}, 1) == 1, "case2");25 System.out.println("all tests passed");26 }27 28 static void check(boolean cond, String name) {29 if (!cond) throw new AssertionError("FAILED: " + name);30 System.out.println(" PASS " + name);31 }32}