class Solution{ int m = (int)1e9+7; public int countPartitions(int n, int d, int nums[]){ //s1-s2 = d -> s1 = total-s1 -> s2 = (totalsum-d/2) //find count of subsets which is equal to (d-totalsum/2) //(d-totalsum)/2 should be > 0 && should be even int t = 0; for(int a : nums) t+=a; int sum = (t-d)/2; if(sum < 0 || (t-d)%2 != 0) return 0; int[][] dp = new int[n][sum+1]; //base case if(nums[0] == 0) dp[0][0] = 2; else dp[0][0] = 1; if(nums[0] != 0 && nums[0] <= sum) dp[0][nums[0]] = 1; //rest of the recursion logic for(int i = 1 ;i < n ; i++){ for(int j = 0 ; j < sum+1 ; j++){ int notake = dp[i-1][j]; int take = 0; if(j - nums[i] >= 0) take = dp[i-1][j-nums[i]]; dp[i][j]=(take+notake)%m; } } return dp[n-1][sum]; } //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)%m; } }