{"id":761,"date":"2025-07-22T14:41:13","date_gmt":"2025-07-22T09:11:13","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=761"},"modified":"2025-07-22T14:41:14","modified_gmt":"2025-07-22T09:11:14","slug":"combination-sum-iii","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/","title":{"rendered":"Combination Sum III | Leetcode 216 | Optimal Solution in Python"},"content":{"rendered":"\n<p>Find all valid combinations of&nbsp;<code>k<\/code>&nbsp;numbers that sum up to&nbsp;<code>n<\/code>&nbsp;such that the following conditions are true:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Only numbers\u00a0<code>1<\/code>\u00a0through\u00a0<code>9<\/code>\u00a0are used.<\/li>\n\n\n\n<li>Each number is used\u00a0<strong>at most once<\/strong>.<\/li>\n<\/ul>\n\n\n\n<p>Return&nbsp;<em>a list of all possible valid combinations<\/em>. The list must not contain the same combination twice, and the combinations may be returned in any order.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/combination-sum-iii\/description\/\" 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>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> k = 3, n = 7\n<strong>Output:<\/strong> [[1,2,4]]\n<strong>Explanation:<\/strong>\n1 + 2 + 4 = 7\nThere are no other valid combinations.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> k = 3, n = 9<br><strong>Output:<\/strong> [[1,2,6],[1,3,5],[2,3,4]]<br><strong>Explanation:<\/strong><br>1 + 2 + 6 = 9<br>1 + 3 + 5 = 9<br>2 + 3 + 4 = 9<br>There are no other valid combinations.<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> k = 4, n = 1\n<strong>Output:<\/strong> []\n<strong>Explanation:<\/strong> There are no valid combinations.\nUsing 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 &gt; 1, there are no valid combination.<\/pre>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-a9817b0d-f3a0-4c83-b1ec-daa5ffbfca47\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"true\" data-initiallyshow=\"false\"><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<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\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 ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#0-optimal-approach-smart-pruning-with-running-sum\" style=\"\">Optimal Approach (Smart Pruning with Running Sum)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-iii\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/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-optimal-approach-smart-pruning-with-running-sum\">Optimal Approach (Smart Pruning with Running Sum)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Instead of generating all combinations and then filtering, why not be smart about it? As we build our combination, we can keep track of the running sum. If the sum already equals our target and we have k numbers, we found a solution! If the sum exceeds our target or we have more than k numbers, we can immediately backtrack &#8211; no need to continue down that path. It&#8217;s like being a smart lottery player who stops picking numbers as soon as they see their total is already too high or they have enough numbers.<\/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>Track Running Sum<\/strong>: Pass the current sum as a parameter instead of calculating it repeatedly.<\/li>\n\n\n\n<li><strong>Early Success Detection<\/strong>: If sum equals n AND we have k numbers, add to result immediately.<\/li>\n\n\n\n<li><strong>Smart Pruning<\/strong>: If sum > n OR length > k, return immediately (early termination).<\/li>\n\n\n\n<li><strong>Avoid Duplicates<\/strong>: Use\u00a0<code>last<\/code>\u00a0parameter to ensure we only pick numbers in ascending order.<\/li>\n\n\n\n<li><strong>Efficient Backtracking<\/strong>: Each recursive call is O(1) since we don&#8217;t recalculate sums.<\/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 func(self, n, Sum, last, nums, k, ans):\n        # Base case: Found valid combination\n        if Sum == n and len(nums) == k:\n            ans.append(list(nums))  # Make a copy to preserve state\n            return\n        \n        # Pruning: Early termination for invalid paths\n        if Sum &gt; n or len(nums) &gt; k:\n            return\n\n        # Try numbers from last to 9 (ascending order, no duplicates)\n        for i in range(last, 10):\n            nums.append(i)\n            self.func(n, Sum + i, i + 1, nums, k, ans)  # Update sum and next start\n            nums.pop()  # Backtrack\n\n    def combinationSum3(self, k, n):\n        ans = []\n        nums = []\n        self.func(n, 0, 1, nums, k, ans)  # Start with sum=0, last=1\n        return ans\" 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\">func<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">Sum<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">last<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">nums<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">k<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">ans<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: Found valid combination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> Sum == n <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums) == k:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            ans.append(<\/span><span style=\"color: #4EC9B0\">list<\/span><span style=\"color: #D4D4D4\">(nums))  <\/span><span style=\"color: #6A9955\"># Make a copy to preserve state<\/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\"># Pruning: Early termination for invalid paths<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> Sum &gt; n <\/span><span style=\"color: #569CD6\">or<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(nums) &gt; k:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">return<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Try numbers from last to 9 (ascending order, no duplicates)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> i <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(last, <\/span><span style=\"color: #B5CEA8\">10<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            nums.append(i)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(n, Sum + i, i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, nums, k, ans)  <\/span><span style=\"color: #6A9955\"># Update sum and next start<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            nums.pop()  <\/span><span style=\"color: #6A9955\"># Backtrack<\/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\">combinationSum3<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">k<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">n<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        ans = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        nums = []<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.func(n, <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, nums, k, ans)  <\/span><span style=\"color: #6A9955\"># Start with sum=0, last=1<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> ans<\/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 optimal solution uses smart pruning to avoid unnecessary exploration. By tracking the running sum (<code>Sum<\/code>), we can immediately detect success (<code>Sum == n and len(nums) == k<\/code>) or failure (<code>Sum &gt; n or len(nums) &gt; k<\/code>) conditions. The&nbsp;<code>last<\/code>&nbsp;parameter ensures we only consider numbers in ascending order, preventing duplicate combinations like&nbsp;<a rel=\"noreferrer noopener\" target=\"_blank\" href=\"https:\/\/leetcode.com\/problems\/combination-sum-iii\/description\/\"><\/a>&nbsp;and&nbsp;<a rel=\"noreferrer noopener\" target=\"_blank\" href=\"https:\/\/leetcode.com\/problems\/combination-sum-iii\/description\/\"><\/a>.&nbsp;Each recursive call updates the sum incrementally rather than recalculating it, making the operation O(1).<\/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[\"func(n=7, Sum=0, last=1, nums=[], k=3)&lt;br\/>Find 3 numbers from 1-9 that sum to 7\"]\n    \n    %% Level 0: try numbers 1-9\n    Root --- A[\"Try 1&lt;br\/>nums=[1], Sum=1&lt;br\/>last=2\"]\n    Root --- B[\"Try 2&lt;br\/>nums=[2], Sum=2&lt;br\/>last=3\"]\n    Root --- C[\"Try 3&lt;br\/>nums=[3], Sum=3&lt;br\/>last=4\"]\n    Root --- D[\"Try 4&lt;br\/>nums=[4], Sum=4&lt;br\/>last=5\"]\n    Root --- E[\"Try 5,6,7,8,9&lt;br\/>Sum > 7 when k=3&lt;br\/>Pruned early\"]\n    \n    %% Level 1 from [1]: try numbers 2-9\n    A --- A1[\"Try 2&lt;br\/>nums=[1,2], Sum=3&lt;br\/>last=3\"]\n    A --- A2[\"Try 3&lt;br\/>nums=[1,3], Sum=4&lt;br\/>last=4\"]\n    A --- A3[\"Try 4&lt;br\/>nums=[1,4], Sum=5&lt;br\/>last=5\"]\n    A --- A4[\"Try 5&lt;br\/>nums=[1,5], Sum=6&lt;br\/>last=6\"]\n    A --- A5[\"Try 6,7,8,9&lt;br\/>Sum + min_remaining > 7&lt;br\/>Pruned\"]\n    \n    %% Level 1 from [2]: try numbers 3-9  \n    B --- B1[\"Try 3&lt;br\/>nums=[2,3], Sum=5&lt;br\/>last=4\"]\n    B --- B2[\"Try 4,5,6,7,8,9&lt;br\/>Sum + remaining > 7&lt;br\/>Pruned\"]\n    \n    %% Level 1 from [3]: try numbers 4-9\n    C --- C1[\"Try 4,5,6,7,8,9&lt;br\/>Sum + remaining > 7&lt;br\/>All pruned\"]\n    \n    %% Level 1 from [4]: try numbers 5-9\n    D --- D1[\"Try 5,6,7,8,9&lt;br\/>Sum already 4, need 2 more&lt;br\/>Min remaining = 5+6=11 > 3&lt;br\/>All pruned\"]\n    \n    %% Level 2 from [1,2]: try numbers 3-9\n    A1 --- A1a[\"Try 3&lt;br\/>nums=[1,2,3], Sum=6&lt;br\/>len=3 but Sum\u22607\"]\n    A1 --- A1b[\"Try 4&lt;br\/>nums=[1,2,4], Sum=7&lt;br\/>len=3 and Sum=7\"]\n    A1 --- A1c[\"Try 5&lt;br\/>nums=[1,2,5], Sum=8&lt;br\/>Sum > 7, return\"]\n    A1 --- A1d[\"Try 6,7,8,9&lt;br\/>Sum > 7&lt;br\/>All pruned\"]\n    \n    %% Level 2 from [1,3]: try numbers 4-9\n    A2 --- A2a[\"Try 4&lt;br\/>nums=[1,3,4], Sum=8&lt;br\/>Sum > 7, return\"]\n    A2 --- A2b[\"Try 5,6,7,8,9&lt;br\/>Sum > 7&lt;br\/>All pruned\"]\n    \n    %% Level 2 from [1,4]: try numbers 5-9\n    A3 --- A3a[\"Try 5&lt;br\/>nums=[1,4,5], Sum=10&lt;br\/>Sum > 7, return\"]\n    A3 --- A3b[\"Try 6,7,8,9&lt;br\/>Sum > 7&lt;br\/>All pruned\"]\n    \n    %% Level 2 from [1,5]: try numbers 6-9\n    A4 --- A4a[\"Try 6&lt;br\/>nums=[1,5,6], Sum=12&lt;br\/>Sum > 7, return\"]\n    A4 --- A4b[\"Try 7,8,9&lt;br\/>Sum > 7&lt;br\/>All pruned\"]\n    \n    %% Level 2 from [2,3]: try numbers 4-9\n    B1 --- B1a[\"Try 4&lt;br\/>nums=[2,3,4], Sum=9&lt;br\/>Sum > 7, return\"]\n    B1 --- B1b[\"Try 5,6,7,8,9&lt;br\/>Sum > 7&lt;br\/>All pruned\"]\n    \n    %% Results\n    A1a --- Fail1[\"len=3 but Sum=6\u22607&lt;br\/>\u274c Return\"]\n    A1b --- Success1[\"len=3 and Sum=7&lt;br\/>\u2705 Add [1,2,4] to result\"]\n    A1c --- Fail2[\"Sum=8 > 7&lt;br\/>\u274c Return (pruning)\"]\n    \n    %% Final result\n    Success1 --- Final[\"Final Result: [[1,2,4]]\"]\n\n    %% Styling\n    style Success1 fill:#90EE90\n    style Final fill:#90EE90\n    \n    style Fail1 fill:#DDA0DD\n    style Fail2 fill:#FFB6C1\n    style A2a fill:#FFB6C1\n    style A3a fill:#FFB6C1\n    style A4a fill:#FFB6C1\n    style B1a fill:#FFB6C1\n    style A1c fill:#FFB6C1\n    \n    style E fill:#FFE4B5\n    style A5 fill:#FFE4B5\n    style B2 fill:#FFE4B5\n    style C1 fill:#FFE4B5\n    style D1 fill:#FFE4B5\n    \n    style Root fill:#E6E6FA\n<\/pre><\/div>\n\n\n\n<p>Click <mark style=\"background-color:#ffffff\" class=\"has-inline-color has-vivid-red-color\"><strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqtV11v2zYU_SsEhwItwmQmKUqyMBWwLftpBYamT42DgrboWJhEBfrYlgZ53EOB_oQN2G_rLxklUR_Wh5uu80Ng8d5zeHh477XyCPexL6AD7xJ-fwTvvK0E6vM2jrObLTzkcv9SuhYC13nkzhAIeZq5GAGZR6l7c4vAry599dMu-fH1JpA-oEVgJ5IUHJI4AvhyDrIjz0CaRyCLgbWFtxV_9ffFC_Cz-E2EYOaALHlowArXygCXl5dgocS8Uxm43KvaHd9Wsqq1UhlpNmiQS40kHSTRSNIi6RC50kjaQVKNpC3SGCI9jTQ6SEMjjRbJhsi1RjJkIgvZaF5mKxx4DSzw-1HIwvFy8Zckl8IHgifhw5SvuLoHZdWpwaQ2eFG5i0dMwogMD9vapJFkxCSM6PCwRh9JR0zCqLaJjdmkkUZt0gmSaaTZIs0-kmlk39wLEAXyQyIiHshA3hVmdzz-mruk5y5VZa9zl1UN4hGXSOMSG3NJI2t_DTQsiQvwXxXTnmKjrodVVfn4G3ddhCG4f9bORm9nVu_sVZ2DJxuAh4ngfqEJSKEKn4AoTkQZfhPIjigXsAvTxVipo89UR-o-QSN3qSsI61bhoxXf3qauPyFdCnZ5Vqx9-fRPO_oaot1oA5CmBawOEVfDtVwb0uxHu4E0_WB3RwhSPmV5Ioc0_kRrPP-KWxMny2tB9NTgo2enzdm_Irqm2Z0bl98se7I2F1SPLD7qtdF4jWfnddc8u__RbNZTbTaqDT0ua9Xm6bxEZq2anFdd89Sqv1czmS6QJdYDc6xASKdA5mclNzTfVyBvRZqHWVp3Ci9JNzwIiyl10uGuWfR4Sfjl788K2GuyXQm9zvd7kaYtumnrCvnXn2Dh-0BPgeKNKSkVdIj2jYbil6FsleYo7c7gZXEkNQxfDQ-lXtR4WBOXi7WsiroIK-oqrXLAATda023J13BdZw-h2qV6TtWDaMkOQRg6P8xn6_V81k2oiIfRk5zCY53jeYuZ5_WjREc3m6W5wt2oGi7TMXomZkzHVD1O49SdDGPdjHUTXxtLdoJlk6ElmQyt8GTIGwt1E8o3zSplba7NzWIrIVIv_4EPnSzJBYKRSNQvqXqEjwVwC7OjiMQWOuqrLw68rMetfFKwey7fx3FUI5M4vztC58DDVD3l9z7PhBdw9Z9F1KwmQvoiWcW5zKBDZtgoWaDzCP-ADjbYlY2xTUzLYhRT20bwATrUumIzi-A5sQkx7Ln1hODHcl98pfLonBHGbIYtCz_9C2ZTsmk\" target=\"_blank\" rel=\"noreferrer noopener\">here<\/a> <\/strong><\/mark>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(C(9,k)) in worst case, but with significant pruning in practice<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>\u00a0O(k) &#8211; Recursion depth and current combination storage<\/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 is like being a smart shopper with a budget, as you add items to your cart, you keep a running total. If you hit your budget exactly with the right number of items, perfect! If you go over budget or have too many items, you immediately put the last item back and try something else.<\/p>\n\n\n\n<p>The&nbsp;<strong>optimal approach<\/strong>&nbsp;is significantly better in practice due to early pruning, even though the worst-case complexity is similar. The key optimizations are:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Running sum tracking<\/strong>\u00a0&#8211; avoids recalculating sums<\/li>\n\n\n\n<li><strong>Early success detection<\/strong>\u00a0&#8211; stops as soon as valid combination is found<\/li>\n\n\n\n<li><strong>Smart pruning<\/strong>\u00a0&#8211; eliminates invalid paths immediately<\/li>\n\n\n\n<li><strong>Ascending order generation<\/strong>\u00a0&#8211; prevents duplicate combinations naturally<\/li>\n<\/ol>\n\n\n\n<p>The beauty of Combination Sum III lies in its constrained problem space (only digits 1-9) which makes the backtracking approach very efficient with proper pruning. The optimal solution demonstrates excellent backtracking principles that apply to many combinatorial 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","protected":false},"excerpt":{"rendered":"<p>Find all valid combinations of&nbsp;k&nbsp;numbers that sum up to&nbsp;n&nbsp;such that the following conditions are true: Return&nbsp;a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order. Here&#8217;s the [Problem Link] to begin with. Example 1: Input: k = 3, n =<\/p>\n","protected":false},"author":1,"featured_media":762,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[32,19],"class_list":{"0":"post-761","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\/combination-sum-3-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\/761","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=761"}],"version-history":[{"count":1,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/761\/revisions"}],"predecessor-version":[{"id":763,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/761\/revisions\/763"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/762"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=761"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=761"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=761"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}