Given an array arr of non-negative integers and an integer target, the task is to count all subsets of the array whose sum is equal to the given target.
Here’s the [Problem Link] to begin with.
Examples:
Input: arr[] = [5, 2, 3, 10, 6, 8], target = 10
Output: 3
Explanation: The subsets {5, 2, 3}, {2, 8}, and {10} sum up to the target 10.
Input: arr[] = [2, 5, 1, 4, 3], target = 10
Output: 3
Explanation: The subsets {2, 1, 4, 3}, {5, 1, 4}, and {2, 5, 3} sum up to the target 10.
Input: arr[] = [5, 7, 8], target = 3
Output: 0 Explanation: There are no subsets of the array that sum up to the target 3.
Input: arr[] = [35, 2, 8, 22], target = 0
Output: 1 Explanation: The empty subset is the only subset with a sum of 0.
Constraints:
1 ≤ arr.size() ≤ 103
0 ≤ arr[i] ≤ 103
0 ≤ target ≤ 103
Contents:
[show]
Solution 1: Recursion (Brute Force)
Intuition and Approach
At each index, you can:
- Pick the current element if it doesn’t exceed the remaining total.
- Not pick it.
Base case at index 0:
- If total == 0 and arr == 0 → 2 ways (include/exclude zero).
- Else if total == 0 or arr == total → 1 way.
- Otherwise → 0 ways.
This explores all subsets and sums counts.
Code Implementation
class Solution:
def solve(self, index, total, arr):
# Base case at first element (handle zero carefully)
if index == 0:
if total == 0 and arr == 0:
return 2
if total == 0 or arr == total:
return 1
return 0
# Try pick if feasible, else 0
if arr[index] > total:
pick = 0
else:
pick = self.solve(index - 1, total - arr[index], arr)
# Not pick path
not_pick = self.solve(index - 1, total, arr)
# Total ways = pick + not_pick
return pick + not_pick
def perfectSum(self, arr, target):
n = len(arr)
return self.solve(n - 1, target, arr)Code Explanation
- The base handles all zero/target relationships at index 0 to ensure correct counting.
- For each index, add ways from picking and not picking when possible.
- Returns total number of valid subsets.
Time and Space Complexity
- Time: Exponential (O(2^n)) due to exploring all subsets.
- Space: O(n) recursion depth.
Solution 2: Memoization (Top-Down DP)
Intuition and Approach
Same recursion, but cache results for (index, total) to avoid recomputation.
- dp[index][total] stores number of ways to reach sum total using elements up to index.
Code Implementation
class Solution:
def solve(self, index, total, arr, dp):
# Base case at first element
if index == 0:
if total == 0 and arr == 0:
return 2
if total == 0 or arr == total:
return 1
return 0
# Return cached value if present
if dp[index][total] != -1:
return dp[index][total]
# Pick if feasible
if arr[index] > total:
pick = 0
else:
pick = self.solve(index - 1, total - arr[index], arr, dp)
# Not pick
not_pick = self.solve(index - 1, total, arr, dp)
dp[index][total] = pick + not_pick
return dp[index][total]
def perfectSum(self, arr, target):
n = len(arr)
dp = [[-1 for _ in range(target + 1)] for _ in range(n)]
return self.solve(n - 1, target, arr, dp)Code Explanation
- Adds memoization to cut exponential recomputation.
- The base case logic with zero handling remains identical for correctness.
Time and Space Complexity
- Time: O(n × target) states, O(1) per state → O(n × target).
- Space: O(n × target) for dp + O(n) recursion stack.
Solution 3: Tabulation (Bottom-Up DP)
Intuition and Approach
Build dp iteratively:
- dp[i][t] = number of ways to make sum t using elements up to index i.
- Initialize row 0 carefully to account for zero.
- Transition: dp[i][t] = dp[i-1][t] (not pick) + (dp[i-1][t – arr[i]] if arr[i] ≤ t else 0).
Code Implementation
class Solution:
def perfectSum(self, arr, target):
n = len(arr)
dp = [[0 for _ in range(0, target + 1)] for _ in range(n)]
# Base init for index 0 (handle zero specially)
if arr[0] == 0:
dp = 2
else:
dp = 1
if arr <= target:
dp[arr] = 1
# Fill table
for index in range(1, n):
for total in range(0, target + 1):
if arr[index] > total:
pick = 0
else:
pick = dp[index - 1][total - arr[index]]
not_pick = dp[index - 1][total]
dp[index][total] = pick + not_pick
return dp[n - 1][target]Code Explanation
- Base initialization:
- If arr == 0 → dp = 2 (include/exclude zero).
- Else dp = 1, and if arr ≤ target, dp[arr] = 1.
- Transitions count ways by adding pick and not_pick counts.
Time and Space Complexity
- Time: O(n × target)
- Space: O(n × target)
Solution 4: Tabulation (Space Optimization)
Intuition and Approach
Use two 1D arrays (prev and curr) since each row depends only on previous row.
Code Implementation
class Solution:
def perfectSum(self, arr, target):
n = len(arr)
prev = [0 for _ in range(0, target + 1)]
# Base init for index 0
if arr == 0:
prev = 2
else:
prev = 1
if arr <= target:
prev[arr] = 1
# Build with rolling arrays
for index in range(1, n):
curr = [0 for _ in range(0, target + 1)]
for total in range(0, target + 1):
if arr[index] > total:
pick = 0
else:
pick = prev[total - arr[index]]
not_pick = prev[total]
curr[total] = pick + not_pick
prev = curr
return prev[target]Code Explanation
- Mirrors the full table logic with O(target) space.
- Base and transitions remain identical, ensuring correctness with zeros.
Time and Space Complexity
- Time: O(n × target)
- Space: O(target)
Tips and Edge Cases
- Zeros: The base case and first-row initialization must treat arr == 0 specially, as it doubles the count for sum 0 at index 0.
- Large counts: Depending on platform constraints, you might need modulus; your current code returns raw counts, which is typically fine unless specified otherwise.
- Order doesn’t matter: We count subsets (combinations), not sequences, so the DP uses each element at most once.
Conclusion
The Perfect Sum Problem is a counting variant of Subset Sum where careful handling of zeros is crucial. Starting from recursion for clarity, you can optimize to memoization and tabulation; the space-optimized tabulation is the most interview-friendly with O(n × target) time and O(target) space while preserving correctness.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.