{"id":757,"date":"2025-07-22T14:31:56","date_gmt":"2025-07-22T09:01:56","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=757"},"modified":"2025-07-22T14:31:57","modified_gmt":"2025-07-22T09:01:57","slug":"subset-sums","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/subset-sums\/","title":{"rendered":"Subset Sums | GFG Practice | Brute and Optimal Solution"},"content":{"rendered":"\n<p>Given a array&nbsp;<strong><code>arr<\/code>&nbsp;<\/strong>of integers, return the sums of all subsets in the list.&nbsp; Return the sums in any order.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/subset-sums2234\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>arr[] = [2, 3]\n<strong>Output: <\/strong>[0, 2, 3, 5]\n<strong>Explanation: <\/strong>When no elements are taken then Sum = 0. When only 2 is taken then Sum = 2. When only 3 is taken then Sum = 3. When elements 2 and 3 are taken then Sum = 2+3 = 5.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>arr[] = [1, 2, 1]\n<strong>Output: <\/strong>[0, 1, 1, 2, 2, 3, 3, 4]<br><strong>Explanation: <\/strong>The possible subset sums are 0 (no elements), 1 (either of the 1's), 2 (the element 2), and their combinations.<\/pre>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input: <\/strong>arr[] = [5, 6, 7]\n<strong>Output: <\/strong>[0, 5, 6, 7, 11, 12, 13, 18]\n<strong>Explanation: <\/strong>The possible subset sums are 0 (no elements), 5, 6, 7, and their combinations.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><br>1 \u2264 arr.size() \u2264 15<br>0 \u2264 arr[i] \u2264 10<sup>4<\/sup><\/p>\n\n\n<div class=\"wp-block-ub-table-of-contents-block ub_table-of-contents\" id=\"ub_table-of-contents-1472de93-6a17-44d1-9754-929e11ed1451\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"false\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"true\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column \">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#0-solution-1-brute-force-approach-maintaining-explicit-subset\" style=\"\">Solution 1: Brute Force Approach (Maintaining Explicit Subset)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#8-solution-2-optimal-approach-running-sum\" style=\"\">Solution 2: Optimal Approach (Running Sum)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/subset-sums\/#16-summary\" style=\"\">Summary<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"0-solution-1-brute-force-approach-maintaining-explicit-subset\">Solution 1: Brute Force Approach (Maintaining Explicit Subset)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like collecting items in a bag and calculating the total value each time! For every element in the array, we have two choices: either include it in our current subset or exclude it. We maintain an explicit list of the current subset and calculate its sum when we&#8217;ve made decisions for all elements. It&#8217;s like trying every possible combination of items and writing down the total value of each combination.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"2-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Use Include\/Exclude Pattern<\/strong>: For each element, try including it in the subset and excluding it.<\/li>\n\n\n\n<li><strong>Maintain Explicit Subset<\/strong>: Keep track of the current subset as a list.<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: When we&#8217;ve processed all elements (index >= len(nums)), calculate sum of current subset and add to result.<\/li>\n\n\n\n<li><strong>Backtracking<\/strong>: After exploring the &#8220;include&#8221; path, remove the element (pop) and explore the &#8220;exclude&#8221; path.<\/li>\n\n\n\n<li><strong>Sort Result<\/strong>: Sort the final result as required by the problem.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, nums, index, subset, result):\n        # Base case: processed all elements\n        if index &gt;= len(nums):\n            result.append(sum(subset))  # Calculate sum of current subset\n            return\n        \n        # Choice 1: Include current element\n        subset.append(nums[index])\n        self.solve(nums, index + 1, subset, result)\n        \n        # Backtrack: Remove current element  \n        subset.pop()\n        \n        # Choice 2: Exclude current element\n        self.solve(nums, index + 1, subset, result)\n\n    def subsetSums(self, arr):\n        result = []\n        self.solve(arr, 0, [], result)\n        result.sort()  # Sort as required by problem\n        return result\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">subset<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: processed all elements<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            result.append(<\/span><span style=\"color: #DCDCAA\">sum<\/span><span style=\"color: #D4D4D4\">(subset))  <\/span><span style=\"color: #6A9955\"># Calculate sum of current subset<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 1: Include current element<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        subset.append(nums[index])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(nums, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, subset, result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Backtrack: Remove current element  <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        subset.pop()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 2: Exclude current element<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(nums, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, subset, result)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">subsetSums<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(arr, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, [], result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result.sort()  <\/span><span style=\"color: #6A9955\"># Sort as required by problem<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> result<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This solution uses the classic include\/exclude backtracking pattern. We maintain an explicit subset list throughout the recursion. At each step, we first try including the current element (append to subset, recurse), then backtrack by removing it (pop), and try excluding it (recurse without the element). When we reach the base case (processed all elements), we calculate the sum of the current subset and add it to our results. The key insight is that we explore all 2^n possible subsets systematically.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-dry-run\">Dry Run<\/h3>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"solve(arr=[2,3], index=0, subset=[])&lt;br\/>Generate all subset sums\"]\n    \n    %% Level 0: index=0, element=2\n    Root --- A[\"Include 2&lt;br\/>subset=[2]&lt;br\/>index=1\"]\n    Root --- B[\"Exclude 2&lt;br\/>subset=[]&lt;br\/>index=1\"]\n    \n    %% Level 1 from Include 2: index=1, element=3\n    A --- A1[\"Include 3&lt;br\/>subset=[2,3]&lt;br\/>index=2\"]\n    A --- A2[\"Exclude 3&lt;br\/>subset=[2]&lt;br\/>index=2\"]\n    \n    %% Level 1 from Exclude 2: index=1, element=3\n    B --- B1[\"Include 3&lt;br\/>subset=[3]&lt;br\/>index=2\"]\n    B --- B2[\"Exclude 3&lt;br\/>subset=[]&lt;br\/>index=2\"]\n    \n    %% Level 2: Base case - index >= len(nums)\n    A1 --- Result1[\"index=2 >= len(arr)&lt;br\/>\u2705 sum([2,3]) = 5&lt;br\/>Add 5 to result\"]\n    A2 --- Result2[\"index=2 >= len(arr)&lt;br\/>\u2705 sum([2]) = 2&lt;br\/>Add 2 to result\"]\n    B1 --- Result3[\"index=2 >= len(arr)&lt;br\/>\u2705 sum([3]) = 3&lt;br\/>Add 3 to result\"]\n    B2 --- Result4[\"index=2 >= len(arr)&lt;br\/>\u2705 sum([]) = 0&lt;br\/>Add 0 to result\"]\n    \n    %% Final result\n    Result1 --- Final[\"Final Result: [5, 2, 3, 0]\"]\n    Result2 --- Final\n    Result3 --- Final\n    Result4 --- Final\n\n    %% Styling\n    style Result1 fill:#90EE90\n    style Result2 fill:#90EE90\n    style Result3 fill:#90EE90\n    style Result4 fill:#90EE90\n    style Final fill:#90EE90\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>Click <strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqNlNFumzAUhl_F8lQpkUhmbCABjUrJmk6TdtXtaiEXNDgJkjGRgSpdlMu9xZ5uTzJjJ4auoCQXBPv4_P_nw7GPcJ0nFAZwK-L9Dvx4iDiQv6c8L5cRLHL2QgexEOESW2RlgZQn9BAiCxTVc0HLcLkafnoWH--_UE5FXFIQM3aOyb-siOBKC-rn3R34Rl8oAyhopCijGeVliBtrMBqNwEwCfOVrViUUYOVyMcUrNdQKtvEwmXOZuTh0ZXYn_gdng43IM2C8L6x2w0p0ykyD2i1S8pZUVq1liY3lORO3SEn_HvEVVLPZftS5rkw_ag_oOa8f9CZOCTaPCwrW9WOkIcF9CBjlAy77ZHiuiq3cnmhRsbJGPctelspO1P3298_vur8GqsBDEAJXTc-SBLigzIFQCk21cUsX36SrVLFRxR2q8zYtuUVVsxKjSrpU26zOLapKFBlR1CFqPsdjymN2iepTo4utTFVUWupVOhKApWsBbAFiAbRqDpuuZZPWnibd00572iB9L19Zyrd6XMgBNUyblLHgg48WCx-9j-MrcXIl7vTG9f7fR99o1LeNXrLwFt7jLOLQktdomsCgFBW1YEZFFtdDeKwTI1ju5JGMYCBfE7qJ1QeK-Emm7WP-M8-zS6bIq-0OBpuYFXJU7RN5tT6ksbyjMzMrqOwL8TmveAkD2_NcpQKDIzzAgCB_7LrER97URTa2pxZ8latcPHYm7nQysT3sOP7EO1nwl_JFY8_GLvKn2HMc25n67ukfuY7Xyw\" target=\"_blank\" rel=\"noreferrer noopener\">here<\/a> <\/strong>for better visualization.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"6-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(2^n \u00d7 n) &#8211; We explore 2^n subsets, and for each subset we calculate sum() which takes O(n) time<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(n) &#8211; Maximum depth of recursion stack plus space for the subset list<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"7-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like having a shopping cart and for every item you see, you try putting it in the cart, check the total, then try not putting it in the cart and check that total too. You write down every possible total you can make.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-solution-2-optimal-approach-running-sum\">Solution 2: Optimal Approach (Running Sum)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Instead of maintaining the entire subset and calculating its sum every time, why not just keep track of the running total? It&#8217;s like having a running tally on a calculator &#8211; as you decide to include or exclude each number, you just add to or keep the current total the same. This eliminates the need to recalculate the sum from scratch each time, making each recursive call O(1) instead of O(n).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"10-detailed-approach\">Detailed Approach<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Pass Running Total<\/strong>: Instead of maintaining subset list, pass the current sum as a parameter.<\/li>\n\n\n\n<li><strong>Include Choice<\/strong>: Add current element to the running total and recurse.<\/li>\n\n\n\n<li><strong>Exclude Choice<\/strong>: Keep the running total same and recurse.<\/li>\n\n\n\n<li><strong>Base Case<\/strong>: When all elements processed, add the current total to results.<\/li>\n\n\n\n<li><strong>No Backtracking Needed<\/strong>: Since we&#8217;re not modifying any shared state, no explicit backtracking required.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"11-code\">Code<\/h3>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro cbp-has-line-numbers\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;--cbp-line-number-color:#D4D4D4;--cbp-line-number-width:calc(2 * 0.6 * .875rem);line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"class Solution:\n    def solve(self, nums, total, index, result):\n        # Base case: processed all elements\n        if index &gt;= len(nums):\n            result.append(total)  # Add current running total\n            return\n        \n        # Choice 1: Include current element (add to running total)\n        Sum = total + nums[index]\n        self.solve(nums, Sum, index + 1, result)\n        \n        # Choice 2: Exclude current element (keep same total)\n        Sum = total  # This line is actually redundant\n        self.solve(nums, Sum, index + 1, result)\n\n    def subsetSums(self, arr):\n        result = []\n        self.solve(arr, 0, 0, result)  # Start with total=0, index=0\n        result.sort()\n        return result\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">solve<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">total<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: processed all elements<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> index &gt;= <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            result.append(total)  <\/span><span style=\"color: #6A9955\"># Add current running total<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 1: Include current element (add to running total)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        Sum = total + nums[index]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(nums, Sum, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, result)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Choice 2: Exclude current element (keep same total)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        Sum = total  <\/span><span style=\"color: #6A9955\"># This line is actually redundant<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(nums, Sum, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, result)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">subsetSums<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">arr<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.solve(arr, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, result)  <\/span><span style=\"color: #6A9955\"># Start with total=0, index=0<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result.sort()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> result<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"12-code-explanation\">Code Explanation<\/h3>\n\n\n\n<p>This optimal solution eliminates the need for maintaining an explicit subset list and calculating sums repeatedly. We pass the running total as a parameter &#8211; when we include an element, we pass&nbsp;<code>total + nums[index]<\/code>, when we exclude it, we pass just&nbsp;<code>total<\/code>. Since we&#8217;re not modifying any shared data structure, we don&#8217;t need explicit backtracking. Each recursive call does O(1) work, making this much more efficient than the brute force approach.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"13-dry-run\">Dry Run<\/h3>\n\n\n\n<div class=\"wp-block-merpress-mermaidjs diagram-source-mermaid\"><pre class=\"mermaid\">graph TD\n    Root[\"solve(arr=[2,3], total=0, index=0)&lt;br\/>Generate all subset sums with running total\"]\n    \n    %% Level 0: index=0, element=2\n    Root --- A[\"Include 2&lt;br\/>total = 0 + 2 = 2&lt;br\/>index=1\"]\n    Root --- B[\"Exclude 2&lt;br\/>total = 0&lt;br\/>index=1\"]\n    \n    %% Level 1 from Include 2: index=1, element=3\n    A --- A1[\"Include 3&lt;br\/>total = 2 + 3 = 5&lt;br\/>index=2\"]\n    A --- A2[\"Exclude 3&lt;br\/>total = 2&lt;br\/>index=2\"]\n    \n    %% Level 1 from Exclude 2: index=1, element=3\n    B --- B1[\"Include 3&lt;br\/>total = 0 + 3 = 3&lt;br\/>index=2\"]\n    B --- B2[\"Exclude 3&lt;br\/>total = 0&lt;br\/>index=2\"]\n    \n    %% Level 2: Base case - index >= len(nums)\n    A1 --- Result1[\"index=2 >= len(arr)&lt;br\/>\u2705 Add total=5 to result\"]\n    A2 --- Result2[\"index=2 >= len(arr)&lt;br\/>\u2705 Add total=2 to result\"]\n    B1 --- Result3[\"index=2 >= len(arr)&lt;br\/>\u2705 Add total=3 to result\"]\n    B2 --- Result4[\"index=2 >= len(arr)&lt;br\/>\u2705 Add total=0 to result\"]\n    \n    %% Final result\n    Result1 --- Final[\"Final Result: [5, 2, 3, 0]\"]\n    Result2 --- Final\n    Result3 --- Final\n    Result4 --- Final\n\n    %% Styling\n    style Result1 fill:#90EE90\n    style Result2 fill:#90EE90\n    style Result3 fill:#90EE90\n    style Result4 fill:#90EE90\n    style Final fill:#90EE90\n    \n    style Root fill:#E6E6FA<\/pre><\/div>\n\n\n\n<p>Click <strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqNlN9u2jAUxl_lyFOlVgvMsfOHREslWOk0aVfdrka4SImBSI6DHKdri7jcW-zp9iQzcQhpG1S4iLGPv-_8cmKfLVoUKUMhWslks4afN7EA_bsrCjWLUVnwB3aZSBnNiEXnFqhCJTzCFmQiZY8Rvvp8Lz9df2WCyUQxSDiHsrovmdJDXsLvTK1BVkJkYmW0MZqbDOZ5cQHf2QPjgMODpQWMs5wJFZEjCwwGAxhrom9iwauUAakT15YQAYaPQPRoVo2R3aZqDSbaYPrYa9ArfMVow1IWObQIB2T7iEyNZGx47Q4wfZGPaGCqR7eTl7R5Gznp4L6S98r6cdsXPo07MdU5jYsbXNqbt5GfxsXn4Gq-SVIyWOwfA8MK1xFwJi6FPkxXTW3sOtsdKyuu9sSN7WGrPqzmUP77-wfGadocWVePIGvRscykY0XOtiI9VpMuFT3bivZZdamcs61wj1Vb4dtM6A_RRM2dMPWrU9VRncjsMpEQZq4FxAJqAZ4fr5Kp1VHWXab9y053uUX6oZ647gpmXuoJa5mWGefhhwBPpwF-GyfvxOk7cedk3Lz_2-gLj30vMVum3tS7HSNLt84sRaGSFbNQzmSe7Kdou5fFSK31VYtRqP-mbJnUnycWOy3bJOJXUeQHpSyq1RqFy4SXelZtUt1Qb7JE9-W8XZVMnwX5paiEQqHt-bR2QeEWPaKQ4mDoujTA3sjFNrFHFnrSu1wydHx35Pu2Rxwn8L2dhZ7rvHjo2cTFwcjxvJFPbS_Y_QcyKdIc\" target=\"_blank\" rel=\"noreferrer noopener\">here<\/a> <\/strong>for better visualization.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"14-time-and-space-complexity\">Time and Space Complexity<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Time Complexity:<\/strong>\u00a0O(2^n) &#8211; We still explore 2^n subsets, but each call is now O(1)<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(n) &#8211; Only recursion stack space needed, no extra data structures<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"15-simplifying-it\">Simplifying It<\/h3>\n\n\n\n<p>This approach is like having a mental running total &#8211; as you decide whether to &#8220;buy&#8221; each item, you either add its price to your mental total or keep it the same. You write down your final total at the end of each shopping trip, without needing to look back at what you actually bought.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"16-summary\">Summary<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Approach<\/th><th>Time<\/th><th>Space<\/th><th>Difficulty<\/th><th>Best For<\/th><\/tr><\/thead><tbody><tr><td>Brute Force (Explicit Subset)<\/td><td>O(2^n \u00d7 n)<\/td><td>O(n)<\/td><td>Easy<\/td><td>Understanding the concept<\/td><\/tr><tr><td>Optimal (Running Sum)<\/td><td>O(2^n)<\/td><td>O(n)<\/td><td>Medium<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>optimal approach<\/strong>&nbsp;is clearly superior as it eliminates the redundant sum calculation at each leaf node, reducing the time complexity by a factor of n. The brute force approach is more intuitive for beginners to understand the subset generation process.<\/p>\n\n\n\n<p>The key insight for Subset Sums is realizing that we don&#8217;t need to store the actual subsets, just their sums. By maintaining a running total instead of an explicit subset, we can make each recursive call O(1), which is a common optimization technique in backtracking problems!<\/p>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/codeanddebug.in\/course\/zero-to-hero-python-dsa\" target=\"_blank\" rel=\"noreferrer noopener\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\" target=\"_blank\" rel=\"noreferrer noopener\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\" target=\"_blank\" rel=\"noreferrer noopener\">+91-9712928220<\/a>.<\/em><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given a array&nbsp;arr&nbsp;of integers, return the sums of all subsets in the list.&nbsp; Return the sums in any order. Here&#8217;s the [Problem Link] to begin with. Examples: Input: arr[] = [2, 3] Output: [0, 2, 3, 5] Explanation: When no elements are taken then Sum = 0. When only 2 is taken then Sum =<\/p>\n","protected":false},"author":1,"featured_media":759,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[32,19],"class_list":{"0":"post-757","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-advance-recursion","10":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/subset-sums-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/757","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=757"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/757\/revisions"}],"predecessor-version":[{"id":760,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/757\/revisions\/760"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/759"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=757"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=757"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=757"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}