|
| 1 | +// Solution Shown In Video |
| 2 | + |
| 3 | +publicclassSolution { |
| 4 | +HashMap<String,Integer>dp; |
| 5 | + |
| 6 | +publicintfindTargetSumWays(int[]nums,intS) { |
| 7 | +dp =newHashMap<>(); |
| 8 | +returncalculate(nums,0,0,S); |
| 9 | + } |
| 10 | + |
| 11 | +publicintcalculate(int[]nums,inti,intsum,intS) { |
| 12 | +Strings =i +"," +sum; |
| 13 | + |
| 14 | +if (i ==nums.length) { |
| 15 | +return (sum ==S)?1 :0; |
| 16 | + } |
| 17 | +if(dp.containsKey(s)){ |
| 18 | +returndp.get(s); |
| 19 | + } |
| 20 | + |
| 21 | +intres =calculate(nums,i +1,sum +nums[i],S) +calculate(nums,i +1,sum -nums[i],S); |
| 22 | +dp.put(s,res); |
| 23 | +returnres; |
| 24 | + } |
| 25 | +} |
| 26 | + |
| 27 | +/* Alternative Better Complexity Solution |
| 28 | +------------------------------------------------------------------------------------------------------- |
| 29 | +//Brute-force solution (accepted) |
1 | 30 | // Subset Sum DP solution (Recursive DP solution for java exceeds time limit) |
2 | 31 |
|
3 | | -/* |
4 | 32 | * Calculate for the sum of all the potential positive numbers (targetSum) |
5 | 33 | * |
6 | 34 | * Formula: targetSum = (∑nums + target) / 2 |
|
20 | 48 | * 2 * ∑P = target + ∑nums |
21 | 49 | * (2 * ∑P) / 2 = (target + ∑nums) / 2 |
22 | 50 | * ∑P = (target + ∑nums) / 2 |
23 | | - */ |
24 | | - |
| 51 | + ------------------------------------------------------------------------------- |
25 | 52 | class Solution { |
26 | 53 | public int subsetSum(int[] nums, int targetSum) { |
27 | 54 | int[] dp = new int[targetSum + 1]; |
@@ -50,3 +77,5 @@ public int findTargetSumWays(int[] nums, int target) { |
50 | 77 | : subsetSum(nums, (targetSum + target) / 2); |
51 | 78 | } |
52 | 79 | } |
| 80 | +---------------------------------------------------------------------------------- |
| 81 | +*/ |