FastPrepCount Subsets With a Target Sum
Problems/Count Subsets With a Target Sum

Count Subsets With a Target Sum

Safe Security logoSafe Security● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In the first technical round of a Safe Security SDE-I loop, after project and AI questions, the candidate was asked to count the subsets of an array that add up to a given target. They started with recursion, wrote a 2D dynamic programming solution in a shared document, and were then asked to cut the space down to a 1D array.

The post gives no examples, limits or rules for repeated values. Here the values and the target are positive, and subsets are told apart by position. There are up to 200 values of at most 1000, with a target up to 10^4. The count is returned modulo 10^9 + 7.

Our version is about 85% the same as the reported question.

You are given an array of positive integers nums and a positive integer target. Return the number of subsets of nums whose elements add up to exactly target.

A subset is any choice of positions in nums, and each position can be used at most once. Two subsets are different if they use different positions, even when their values are the same. The answer can be very large, so return it modulo 10^9 + 7.

Function

countSubsets(nums: int[], target: int) → int

Examples

Example 1

nums = [2,3,5,6,8,10]target = 10return = 3

Three subsets add up to 10: {2, 8}, {10} and {2, 3, 5}.

Example 2

nums = [1,1,1,1]target = 2return = 6

Any two of the four positions add up to 2. There are 6 ways to choose two positions out of four, and they count as different subsets even though every value is 1.

Example 3

nums = [5,7]target = 3return = 0

Every value is larger than 3, so no subset adds up to 3. The answer is 0.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • 1 <= target <= 10^4

More Safe Security Onsite Interview questions

  • Merge IntervalsONSITE INTERVIEW · Seen Oct 2026
  • Maximum Subarray SumONSITE INTERVIEW · Seen Jun 2026

Similar questions at other companies

  • 0/1 Knapsack with Weight and Volume LimitsGoogle · ONSITE INTERVIEWGoogle interview questions
  • Maximum Subarray Sum with One DeletionOracle · ONSITE INTERVIEWOracle interview questions
  • Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
  • Coin ChangeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Maximum SubarrayUpstart · ONSITE INTERVIEWUpstart interview questions
  • Smallest Sufficient TeamExpedia · ONSITE INTERVIEWExpedia interview questions
  • Maximum Product SubarrayHartford Financial Services · ONSITE INTERVIEWHartford Financial Services interview questions
  • Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
  • Maximum Value from Circular HousesDigitalOcean · ONSITE INTERVIEWDigitalOcean interview questions
See Safe Security hiring insights
Saved
class Solution {
    public int countSubsets(int[] nums, int target) {
        // Write your code here.
    }
}
Checking account…