Answer to Question #44998 in C++ for Palak

Question

Alia is appearing for the board exams. In order to qualify for the next class Alia need to get exactly X credits. In current semester Alia has to study N number of subjects, and every subject contains C credits. Upon deliberation, Alia has decided that it's better to concentrate on some subjects instead of all. Now Alia is seeking your help to let her know the number of options available for her, such that choosing any one option will promote her to the next standard.
Input Specification:

First line starts with T, number of test cases. Each test case contains N and X, and then next line contains N spaced integers each represent credit (C) associated with i-th subject.

Output Format:

Print the total number of ways available for Alia to qualify for next standard.

Constraints:
1<=T<=10

1<=N<=20

1<=C<=30

1<=X<=500


Sample Input and Output

SNo. Input Output
1
2
5 15
1 2 3 4 5
20 30
30 25 21 25 20 12 19 15 10 28 25 17 21 28 18 27 19 24 21 24



1
3

Answer 1

//Answer on Question#44998 - Progamming - C++
#include <iostream>
using namespace std;
int main() {
   int T; 
   cin >> T;
   while (T-- > 0) {
      static const int MAX_N = 20;
      static const int MAX_X = 500;
      int N, X;
      cin >> N >> X;      
      int C[MAX_N];
      for (int i = 0; i < N; ++i) {
         cin >> C[i];      
      }
      long long d[MAX_N + 1][MAX_X + 1]; // d[i][j] is the number of possibilities to get j gredits using a subset only from the first i subjects
      d[0][0] = 1;
      for (int i = 1; i < X + 1; ++i) {
         d[0][i] = 0;
      }
      for (int i = 1; i < N + 1; ++i) {
         for (int j = 0; j < X + 1; ++j) {
            // d[i][j] is the sum of possibilities when we take the i-th subject and don'ttake it
            d[i][j] = d[i - 1][j]; // we can not take the i-th subject and the number of credits won't change
            if (j >= C[i - 1]) d[i][j] += d[i - 1][j - C[i - 1]]; // we can take the i-th subject and from the number of required credits substract the number of credits of the i-th subject
         }
      }
      cout << d[N][X] << endl;
   }
}