Count Subsets With a Target Sum
Updated
Problem statement
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) → intExamples
Example 1
nums = [2,3,5,6,8,10]target = 10return = 3Three subsets add up to 10: {2, 8}, {10} and {2, 3, 5}.
Example 2
nums = [1,1,1,1]target = 2return = 6Any 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 = 0Every value is larger than 3, so no subset adds up to 3. The answer is 0.
Constraints
1 <= nums.length <= 2001 <= nums[i] <= 10001 <= target <= 10^4
More Safe Security Onsite Interview questions
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