count number od subset having sum eqaul to sum

Solutions on MaxInterview for count number od subset having sum eqaul to sum by the best coders in the world

showing results for - "count number od subset having sum eqaul to sum"
Aiden
30 Apr 2019
1#include <iostream>
2
3using namespace std;
4int solve(int arr[],int n,int sum)
5{
6    int dp[n+1][sum+1];
7    for(int i=0;i<=n;i++)
8    {
9        dp[i][0]=1;
10    }
11    for(int j=1;j<=sum;j++)
12    {
13        dp[0][j]=0;
14    }
15    for(int i=1;i<=n;i++)
16    {
17        for(int j=1;j<=sum;j++)
18        {
19            if(arr[i-1]<=j)
20            {
21                dp[i][j]=dp[i-1][j]+dp[i-1][j-arr[i-1]];
22            }
23            else
24                dp[i][j]=dp[i-1][j];
25        }
26    }
27    return dp[n][sum];
28}
29int main()
30{
31    int n;
32    cin>>n;
33    int arr[n];
34    for(int i=0;i<n;i++)
35    {
36        cin>>arr[i];
37    }
38    int sum;
39    cin>>sum;
40    cout<<solve(arr,n,sum);
41    return 0;
42}
43