problem–>
https://practice.geeksforgeeks.org/problems/subset-sum-problem-1611555638/1/#
code->>
showing seg fault help!!
Subset problem dp
here–>
Hey buddy are you sure you have saved the code?
Because I am still not able to see Code.
i definately saved this time okay see this–>
// { Driver Code Starts
//Initial template for C++
#include<bits/stdc++.h>
using namespace std;
// } Driver Code Ends
//User function template for C++
class Solution{
public:
bool isSubsetSum(int n, int set[], int sum){
// code here
bool subset[n+1][sum+1];
for(int i=0;i<=n;i++){
subset[i][0]=true;
}
for(int i=1;i<=sum;i++){
subset[0][i]=false;
}
for(int i=1;i<=n;i++){
for(int j=1;i<=sum;j++){
if(j<set[i-1]){
subset[i][j]=subset[i-1][j];
}
if(j>=set[i-1]){
subset[i][j]=subset[i-1][j]||subset[i-1][j-set[i-1]];
}
}
}
return subset[n][sum];
}
};
// { Driver Code Starts.
int main()
{
int t;
cin>>t;
while(t--)
{
int N, sum;
cin >> N;
int arr[N];
for(int i = 0; i < N; i++){
cin >> arr[i];
}
cin >> sum;
Solution ob;
cout << ob.isSubsetSum(N, arr, sum) << endl;
}
return 0;
}
// } Driver Code Endsfor me it code is coming
Okay good
Tell me now are you getting segmentation fault during submission or for the sample test case as well?
for first test case itself it is showing seg fault
1
6
3 34 4 12 5 2
30
My approach–>
basic recursion base case 1.if(sum==0) return true; 2.if(n==0 and sum>0) return false; recursive case 1.including current element from last and see what recursion says fun(array,n-1,sum-array[n-1]); 2.excluding the current element from last and see what recursion says fun(array,n-1,sum); bool ans=1||2;(see if any of recursive call return true;) return ans;
storing this in a table
bottom up approach ->dp[i–>array index][j–>current sum in recursion state]
if(j<arr[i-1]){
dp[i][j]=dp[i][j-1];(not including this element because sum become negative)
}
else if(j>=arr[i]){
dp[i][j]=dp[i][j-1]||dp[i][j];
}
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.