Perfect Sum Problem — Solution in Python, Java & C++
Perfect Sum Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Perfect Sum Problem is a medium coding problem on arrays and dynamic programming, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array of non-negative integers arr and an integer target, count the subsets of arr whose elements add up to exactly target.
Subsets are told apart by the positions they take, not by their values: in [1,1] the two single-element subsets {arr[0]} and {arr[1]} are different. Elements equal to 0 matter too — adding or leaving out a zero gives a different subset with the same sum.
The count can be very large, so return it modulo 10^9 + 7.
Example 1
Input: arr = [5,2,3,10,6,8], target = 10
Output: 3
Explanation: The subsets are {5,2,3}, {2,8} and {10}.
Example 2
Input: arr = [2,5,1,4,3], target = 10
Output: 3
Explanation: {2,5,3}, {5,1,4} and {2,1,4,3}.
Example 3
Input: arr = [0,0,1], target = 1
Output: 4
Explanation: {1} together with any choice of the two zeros: none, the first, the second, or both.
Constraints
1 <= arr.length <= 10000 <= arr[i] <= 10001 <= target <= 1000
Hints for Perfect Sum Problem
Hint 1
This is the subset-sum decision problem turned into counting: instead of whether a sum is reachable, record how many subsets reach it.
Hint 2
Let
ways[s]be the number of subsets (of the elements seen so far) with sums. Initially only the empty subset exists:ways[0] = 1.Hint 3
For each element
a, updateways[s] += ways[s - a]forsfromtargetdown toa, modulo10^9 + 7. Zeros need no special case — witha = 0the update doubles every count, which is exactly right.
How to solve Perfect Sum Problem
Every subset of the first i elements either leaves out element i or includes it. So the number of subsets with sum s after element i is the old count for s plus the old count for s - a. One array of counts, updated in place from high sums to low, carries this forward.
Approach
- Create
ways[0..target], all0exceptways[0] = 1. - For each element
a, loopsfromtargetdown toa:ways[s] = (ways[s] + ways[s - a]) mod (10^9 + 7). - Return
ways[target].
Why it works
The subsets of the first i elements with sum s split into those without element i (counted by the old ways[s]) and those with it (each formed by adding element i to a subset of the first i - 1 elements summing to s - a, counted by the old ways[s - a]). The two groups are disjoint and cover everything. Going downward keeps ways[s - a] at its old value. For a = 0 the loop visits every s and doubles it, matching "take or skip the zero".
Complexity
- Time —
O(n * target) - Space —
O(target)
Pitfalls
- Treating zeros as "don't care" undercounts: each zero doubles the number of subsets.
- Take the modulus after every addition; in typed languages the sum of two residues can pass 2^31, so use 64-bit or subtract the modulus.
- Subsets are distinguished by index, so equal values must not be deduplicated.
Reference solution
Python
from typing import List
def perfectSum(arr: List[int], target: int) -> int:
MOD = 10**9 + 7
ways = [0] * (target + 1)
ways[0] = 1
for a in arr:
for s in range(target, a - 1, -1):
ways[s] = (ways[s] + ways[s - a]) % MOD
return ways[target]Java
public static int perfectSum(int[] arr, int target) {
final long MOD = 1000000007L;
long[] ways = new long[target + 1];
ways[0] = 1;
for (int a : arr) {
for (int s = target; s >= a; s--) ways[s] = (ways[s] + ways[s - a]) % MOD;
}
return (int) ways[target];
}C++
int perfectSum(vector<int>& arr, int target) {
const long long MOD = 1000000007LL;
vector<long long> ways(target + 1, 0);
ways[0] = 1;
for (int a : arr) {
for (int s = target; s >= a; s--) ways[s] = (ways[s] + ways[s - a]) % MOD;
}
return (int) ways[target];
}JavaScript
var perfectSum = function(arr, target) {
var MOD = 1000000007;
var ways = new Array(target + 1).fill(0);
ways[0] = 1;
for (var i = 0; i < arr.length; i++) {
var a = arr[i];
for (var s = target; s >= a; s--) ways[s] = (ways[s] + ways[s - a]) % MOD;
}
return ways[target];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming