Hi all, I've been practising Dp problems from cses set recently and I struck with the question two sets II
Original Problem: https://cses.fi/problemset/task/1093/
I'm trying to solve this using the notion of target sum problem in leetcode, but still getting an error! (21/26 accepted)
Target sum Problem: https://leetcode.com/problems/target-sum/
Below is my code: Please let me know, if any of you find any bug in the solution or the correction needed.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int getNumberofsets(int n,long sum){
vector<vector<long>> dp(n+1,vector<long> (2*sum+1,0));
dp[0][sum-1] = 1;
dp[0][sum+1] = 1;
for(int i = 1 ; i < n ; i++){
for(int total = -sum ; total <= sum ; total++){
if(dp[i-1][sum+total] > 0){
dp[i][sum+i+1+total] += dp[i-1][sum+total]%mod;
dp[i][sum+i+1+total] %= mod;
dp[i][sum-i-1+total] += dp[i-1][sum+total]%mod;
dp[i][sum-i-1+total] %= mod;
}
}
}
return dp[n-1][sum]%mod/2;
}
int main(){
int n;
cin>>n;
long sum = (long)(n*(n+1)/2);
if(sum%2 == 1){
cout<<0<<endl;
} else {
cout<<getNumberofsets(n,sum)<<endl;
}
return 0;
}Thanking in advance!
Comments (1)