部分和数え上げ問題

問題

dp[i][j]
i 番目までの整数の中から(選ぶ、選ばない)
総和を j とするパターン数

const int MOD = 1000000009;

// 入力
int n, A; 
int a[110];

// DPテーブル
int dp[110][10010]; //i番目、総和

int main() {
  cin >> n >> A; //個数、総和
  for (int i = 0; i < n; ++i) cin >> a[i]; //整数

  memset(dp, 0, sizeof(dp));   
  dp[0][0] = 1;                

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= A; ++j) {
      (dp[i+1][j] += dp[i][j]) %= MOD; //a[i]を加算する場合
      if (j >= a[i]) (dp[i+1][j] += dp[i][j-a[i]]) %= MOD; //a[i]を加算しない場合
    }
  }

  cout << dp[n][A] << endl; //n個以下、A以下のパターン数
}