Perfect Sum Problem

Medium
1605.

Perfect Sum Problem

Perfect Sum Problem is a medium coding problem on arrays and dynamic programming, asked in Amazon and Microsoft interviews.

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 <= 1000
  • 0 <= arr[i] <= 1000
  • 1 <= target <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var perfectSum = function(arr, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 1000
  • 0 <= arr[i] <= 1000
  • 1 <= target <= 1000

Hints for Perfect Sum Problem

  1. 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.

  2. Hint 2

    Let ways[s] be the number of subsets (of the elements seen so far) with sum s. Initially only the empty subset exists: ways[0] = 1.

  3. Hint 3

    For each element a, update ways[s] += ways[s - a] for s from target down to a, modulo 10^9 + 7. Zeros need no special case — with a = 0 the 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

  1. Create ways[0..target], all 0 except ways[0] = 1.
  2. For each element a, loop s from target down to a: ways[s] = (ways[s] + ways[s - a]) mod (10^9 + 7).
  3. 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