0
Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Count of Subsets with Given Sum

Acceptance 45.45% Points 30.00

You are given an array of non-negative integers nums and an integer target. Your task is to return the number of subsets whose elements sum exactly to target.

Examples
Example 1

image Input: nums = [1,2,3,3], target = 6
Output: 3
Explanation: The subsets {3, 3}, {1, 2, 3}, and {1, 2, 3} (using the other 3) each sum to 6.

Example 2

image Input: nums = [2,3,5,6,8,10], target = 10
Output: 3
Explanation: The subsets {2, 8}, {10}, and {2, 3, 5} each sum to 10.

Example 3

image Input: nums = [1,1,1], target = 0
Output: 1
Explanation: Only the empty subset sums to 0.

Hints
Hint 1
  • Hint 1: For each element, think about the two choices you have: include it or skip it.
Hint 2
  • Hint 2: Consider how many valid subsets can be formed for smaller sums.
Hint 3
  • Hint 3: Be careful with zero values and the case where target = 0.
Constraints
    • 1 = nums.length = 100
    • 0 = nums[i] = 10³
    • 0 = target = 104
Companies
Expedia Zomato
Topics
Dynamic Programming
Solution.cs C#JavaPythonC++Javascript

Unlock the code editor

Sign in to write, run, and submit your solution against the full test suite.

  • Run code against sample & hidden test cases
  • Save submissions and track your streak
  • Compare with editorial & community solutions