Q-15 Target Sum - LeetCode 494
Sat Sep 09 2023 15:09:21 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int findTargetSumWays(int[] nums, int target) {
/* basically the question is similiar to divide into 2 subsets such that there
difference is equal to target
*/
int t = 0 ,n = nums.length;
for(int a : nums)
t+=a;
int sum = (t-target)/2;
if(sum < 0 || (t-target)%2 != 0) return 0;
return solve(nums , n-1 , sum , new Integer[n][sum+1] );
}
//R-> 2^n M-> n*sum | sc- n + n*sum
public int solve(int nums[] , int i , int sum , Integer[][] dp){
if(i == 0){
if(sum == 0 && nums[0] == 0) return 2; //take = notake , as its 0
//if sum = 0 dont take , if sum = nums[0] take it
else if(sum == 0 || sum == nums[0]) return 1;
else
return 0;
}
if(dp[i][sum] != null)
return dp[i][sum];
int notake = solve(nums , i-1 , sum , dp);
int take = 0;
if(sum - nums[i] >= 0)
take = solve(nums , i-1 , sum-nums[i] , dp);
return dp[i][sum]=take+notake;
}
}
content_copyCOPY
https://leetcode.com/problems/target-sum/
Comments