{"id":887,"date":"2025-08-13T19:24:50","date_gmt":"2025-08-13T13:54:50","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=887"},"modified":"2025-08-13T19:24:51","modified_gmt":"2025-08-13T13:54:51","slug":"perfect-sum-problem","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/perfect-sum-problem\/","title":{"rendered":"Perfect Sum Problem | All 4 DP Solutions in Python"},"content":{"rendered":"\n

Given an array arr<\/code><\/strong> of non-negative integers and an integer target<\/code><\/strong>, the task is to count all subsets of the array whose sum is equal to the given target<\/code>.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Examples:<\/strong><\/p>\n\n\n\n

Input<\/strong>: arr[] = [5, 2, 3, 10, 6, 8], target = 10\nOutput: <\/strong>3\nExplanation<\/strong>: The subsets {5, 2, 3}, {2, 8}, and {10} sum up to the target 10.<\/pre>\n\n\n\n
Input<\/strong>: arr[] = [2, 5, 1, 4, 3], target = 10\nOutput:<\/strong> 3\nExplanation<\/strong>: The subsets {2, 1, 4, 3}, {5, 1, 4}, and {2, 5, 3} sum up to the target 10.<\/pre>\n\n\n\n
Input<\/strong>: arr[] = [5, 7, 8], target = 3
Output:<\/strong> 0\nExplanation<\/strong>: There are no subsets of the array that sum up to the target 3.<\/pre>\n\n\n\n
Input<\/strong>: arr[] = [35, 2, 8, 22], target = 0
Output:<\/strong> 1\nExplanation<\/strong>: The empty subset is the only subset with a sum of 0.<\/pre>\n\n\n\n
Constraints:<\/strong>
1 \u2264 arr.size() \u2264 103
<\/sup>0 \u2264 arr[i] \u2264 103<\/sup>
0 \u2264 target \u2264 103<\/sup><\/p>\n\n\n
\n\t\t\t
\n\t\t\t\t
Contents:<\/div>\n\t\t\t\t
\n\t\t\t
\n\t\t\t\u00a0[show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>
\n\t\t\t
\n\t\t\t\t