Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Count Subsets with Sum K

Medium · Dynamic Programming · Asked at Amazon, Microsoft, Flipkart

Count the subsets (choices of indices, so equal values at different positions count separately) whose elements sum to exactly k. Print the count modulo 1,000,000,007.

Input

First line: n k. Second line: n integers.

Output

The number of subsets modulo 10^9 + 7.

Constraints

ways[s] = number of subsets of the elements seen so far with sum s. For each element x, update s from k down to x: ways[s] += ways[s − x]. Zeros double the count — the same loop handles them.

Example 1

Input

4 3
1 2 2 3

Output

3

Example 2

Input

3 5
0 0 5

Output

4

Hints

  1. ways[s] = number of subsets (of the elements processed so far) with sum s; ways[0] = 1 for the empty subset.
  2. For each element x, update s from k down to x: ways[s] += ways[s − x]. Going downwards uses each element at most once.

Approach

This is 0/1 knapsack counting. Iterating s downward ensures ways[s − x] still refers to subsets that do not include the current element. A zero element doubles every count (take it or not), which the same update does automatically (ways[s] += ways[s]). Reduce modulo 10^9 + 7.

Complexity: O(n · k) time · O(k) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    const long long MOD = 1000000007LL;
    vector<long long> w(k + 1, 0);
    w[0] = 1;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        for (int s = k; s >= x; s--) w[s] = (w[s] + w[s - x]) % MOD;
    }
    cout << w[k] << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, k = data[0], data[1]
MOD = 10**9 + 7
w = [0] * (k + 1)
w[0] = 1
for x in data[2 : 2 + n]:
    for s in range(k, x - 1, -1):
        w[s] = (w[s] + w[s - x]) % MOD
print(w[k])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        long MOD = 1000000007L;
        long[] w = new long[k + 1];
        w[0] = 1;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            for (int s = k; s >= x; s--) w[s] = (w[s] + w[s - x]) % MOD;
        }
        System.out.println(w[k]);
    }
}

Solve Count Subsets with Sum K online · All practice problems