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
- 1 ≤ n ≤ 100
- 0 ≤ a[i] ≤ 1000
- 1 ≤ k ≤ 1000
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
- ways[s] = number of subsets (of the elements processed so far) with sum s; ways[0] = 1 for the empty subset.
- 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