{"id":751,"date":"2025-07-22T14:21:50","date_gmt":"2025-07-22T08:51:50","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=751"},"modified":"2025-07-22T14:21:52","modified_gmt":"2025-07-22T08:51:52","slug":"combination-sum-ii","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/","title":{"rendered":"Combination Sum II | Leetcode 40 | Brute and Optimal Solution"},"content":{"rendered":"\n<p>Given a collection of candidate numbers (<code>candidates<\/code>) and a target number (<code>target<\/code>), find all unique combinations in&nbsp;<code>candidates<\/code>&nbsp;where the candidate numbers sum to&nbsp;<code>target<\/code>.<\/p>\n\n\n\n<p>Each number in&nbsp;<code>candidates<\/code>&nbsp;may only be used&nbsp;<strong>once<\/strong>&nbsp;in the combination.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/leetcode.com\/problems\/combination-sum-ii\/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>Note:<\/strong>&nbsp;The solution set must not contain duplicate combinations.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> candidates = [10,1,2,7,6,1,5], target = 8<br><strong>Output:<\/strong> <br>[<br>[1,1,6],<br>[1,2,5],<br>[1,7],<br>[2,6]<br>]<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted\"><strong>Input:<\/strong> candidates = [2,5,2,1,2], target = 5<br><strong>Output:<\/strong> <br>[<br>[1,2,2],<br>[5]<br>]<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>1 &lt;=&nbsp;candidates.length &lt;= 100<\/code><\/li>\n\n\n\n<li><code>1 &lt;=&nbsp;candidates[i] &lt;= 50<\/code><\/li>\n\n\n\n<li><code>1 &lt;= target &lt;= 30<\/code><\/li>\n<\/ul>\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-bd9c4719-b2b8-4031-80e1-99f7631d4991\" 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-ii\/#0-solution-1-brute-force-approach-using-set-to-handle-duplicates\" style=\"\">Solution 1: Brute Force Approach (Using Set to Handle Duplicates)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#1-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#2-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#3-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#4-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#5-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#6-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#7-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#8-solution-2-optimal-approach-smart-duplicate-avoidance\" style=\"\">Solution 2: Optimal Approach (Smart Duplicate Avoidance)<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#9-intuition\" style=\"\">Intuition<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#10-detailed-approach\" style=\"\">Detailed Approach<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#11-code\" style=\"\">Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#12-code-explanation\" style=\"\">Code Explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#13-dry-run\" style=\"\">Dry Run<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#14-time-and-space-complexity\" style=\"\">Time and Space Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#15-simplifying-it\" style=\"\">Simplifying It<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/combination-sum-ii\/#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-using-set-to-handle-duplicates\">Solution 1: Brute Force Approach (Using Set to Handle Duplicates)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"1-intuition\">Intuition<\/h3>\n\n\n\n<p>Think of this like picking items from a bag where each item can only be picked once, and some items might be identical! Since we can have duplicate numbers in the candidates array, we might generate the same combination multiple times through different paths. For example, if we have and target is 3, we could pick the first 1 and first 2, or first 1 and second 2, both giving . The brute force approach is to generate all possible combinations using standard backtracking and use a set to automatically eliminate duplicates at the end.<\/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>Sort the Array<\/strong>: Sort candidates to help with generating combinations in a consistent order.<\/li>\n\n\n\n<li><strong>Use Set for Results<\/strong>: Use a set to store results as tuples, which automatically handles duplicate combinations.<\/li>\n\n\n\n<li><strong>Standard Backtracking<\/strong>: For each element, try including it (move to next index) or excluding it (move to next index).<\/li>\n\n\n\n<li><strong>Base Cases<\/strong>:\n<ul class=\"wp-block-list\">\n<li>If target equals 0: found a valid combination, add tuple of current subset to set.<\/li>\n\n\n\n<li>If target becomes negative: invalid path, return.<\/li>\n\n\n\n<li>If index reaches array end: no more elements to try, return.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Convert and Return<\/strong>: Convert the set back to a list of lists for the final result.<\/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 padding-bottom-disabled 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 backtrack(self, subset: List[int], index: int, target: int, result, candidates):\n        # Base case: Found a valid combination\n        if target == 0:\n            result.add(tuple(subset.copy()))  # Add as tuple to set for deduplication\n            return\n        # Pruning: Invalid path if target becomes negative\n        elif target &lt; 0:\n            return\n        # Base case: No more candidates to consider\n        if index &gt;= len(candidates):\n            return\n        \n        # Choice 1: Include current candidate\n        subset.append(candidates[index])\n        target -= candidates[index]\n        self.backtrack(subset, index + 1, target, result, candidates)  # Move to next index\n        \n        # Backtrack: Remove the candidate and restore target\n        subset.pop()\n        target += candidates[index]\n        \n        # Choice 2: Exclude current candidate\n        self.backtrack(subset, index + 1, target, result, candidates)\n\n    def combinationSum2(self, candidates: List[int], target: int) -&gt; List[List[int]]:\n        candidates.sort()  # Sort to ensure consistent combination generation\n        result = set()     # Use set to automatically handle duplicates\n        self.backtrack([], 0, target, result, candidates)\n        return list(result)  # Convert set of tuples back to list of lists\" 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\">backtrack<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">subset<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">candidates<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: Found a valid combination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> target == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            result.add(<\/span><span style=\"color: #4EC9B0\">tuple<\/span><span style=\"color: #D4D4D4\">(subset.copy()))  <\/span><span style=\"color: #6A9955\"># Add as tuple to set for deduplication<\/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 style=\"color: #6A9955\"># Pruning: Invalid path if target becomes negative<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">elif<\/span><span style=\"color: #D4D4D4\"> target &lt; <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/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 style=\"color: #6A9955\"># Base case: No more candidates to consider<\/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\">(candidates):<\/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 candidate<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        subset.append(candidates[index])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        target -= candidates[index]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.backtrack(subset, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, target, result, candidates)  <\/span><span style=\"color: #6A9955\"># Move to next index<\/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 the candidate and restore target<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        subset.pop()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        target += candidates[index]<\/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 candidate<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.backtrack(subset, index + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, target, result, candidates)<\/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\">combinationSum2<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">candidates<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        candidates.sort()  <\/span><span style=\"color: #6A9955\"># Sort to ensure consistent combination generation<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        result = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()     <\/span><span style=\"color: #6A9955\"># Use set to automatically handle duplicates<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.backtrack([], <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, target, result, candidates)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">list<\/span><span style=\"color: #D4D4D4\">(result)  <\/span><span style=\"color: #6A9955\"># Convert set of tuples back to list of lists<\/span><\/span><\/code><\/pre><span style=\"display:flex;align-items:flex-end;padding:10px;width:100%;justify-content:flex-end;background-color:#1E1E1E;color:#c7c7c7;font-size:12px;line-height:1;position:relative\">Python<\/span><\/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 sort the candidates first to ensure that identical combinations are generated in the same order (making deduplication easier). The key insight is using a set to store results as tuples &#8211; since tuples are hashable, the set automatically eliminates duplicate combinations. For each candidate, we try including it (subtract from target, move to next index) or excluding it (just move to next index). The backtracking ensures we explore all possibilities, and the set handles the duplicate elimination.<\/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[\"backtrack([], 0, 5)&lt;br\/>candidates=[1,2,2,2,5]&lt;br\/>target=5\"]\n    \n    %% Level 0: index=0, candidate=1\n    Root --- A[\"Include 1&lt;br\/>subset=[1]&lt;br\/>target=4, index=1\"]\n    Root --- B[\"Exclude 1&lt;br\/>subset=[]&lt;br\/>target=5, index=1\"]\n    \n    %% Level 1 from Include 1: index=1, candidate=2\n    A --- A1[\"Include 2&lt;br\/>subset=[1,2]&lt;br\/>target=2, index=2\"]\n    A --- A2[\"Exclude 2&lt;br\/>subset=[1]&lt;br\/>target=4, index=2\"]\n    \n    %% Level 1 from Exclude 1: index=1, candidate=2\n    B --- B1[\"Include 2&lt;br\/>subset=[2]&lt;br\/>target=3, index=2\"]\n    B --- B2[\"Exclude 2&lt;br\/>subset=[]&lt;br\/>target=5, index=2\"]\n    \n    %% Level 2 from [1,2]: index=2, candidate=2\n    A1 --- A1a[\"Include 2&lt;br\/>subset=[1,2,2]&lt;br\/>target=0, index=3\"]\n    A1 --- A1b[\"Exclude 2&lt;br\/>subset=[1,2]&lt;br\/>target=2, index=3\"]\n    \n    %% Level 2 from [1]: index=2, candidate=2\n    A2 --- A2a[\"Include 2&lt;br\/>subset=[1,2]&lt;br\/>target=2, index=3\"]\n    A2 --- A2b[\"Exclude 2&lt;br\/>subset=[1]&lt;br\/>target=4, index=3\"]\n    \n    %% Level 2 from [2]: index=2, candidate=2\n    B1 --- B1a[\"Include 2&lt;br\/>subset=[2,2]&lt;br\/>target=1, index=3\"]\n    B1 --- B1b[\"Exclude 2&lt;br\/>subset=[2]&lt;br\/>target=3, index=3\"]\n    \n    %% Level 2 from []: index=2, candidate=2\n    B2 --- B2a[\"Include 2&lt;br\/>subset=[2]&lt;br\/>target=3, index=3\"]\n    B2 --- B2b[\"Exclude 2&lt;br\/>subset=[]&lt;br\/>target=5, index=3\"]\n    \n    %% Level 3 results\n    A1a --- Success1[\"target=0&lt;br\/>\u2705 Add (1,2,2) to set\"]\n    \n    A1b --- A1b1[\"Include 2&lt;br\/>subset=[1,2,2]&lt;br\/>target=0, index=4\"]\n    A1b --- A1b2[\"Exclude 2&lt;br\/>subset=[1,2]&lt;br\/>target=2, index=4\"]\n    \n    A2a --- A2a1[\"Include 2&lt;br\/>subset=[1,2,2]&lt;br\/>target=0, index=4\"]\n    A2a --- A2a2[\"Exclude 2&lt;br\/>subset=[1,2]&lt;br\/>target=2, index=4\"]\n    \n    A2b --- A2b1[\"Include 2&lt;br\/>subset=[1,2]&lt;br\/>target=2, index=4\"]\n    A2b --- A2b2[\"Exclude 2&lt;br\/>subset=[1]&lt;br\/>target=4, index=4\"]\n    \n    B1a --- B1a1[\"Include 2&lt;br\/>subset=[2,2,2]&lt;br\/>target=-1, index=4\"]\n    B1a --- B1a2[\"Exclude 2&lt;br\/>subset=[2,2]&lt;br\/>target=1, index=4\"]\n    \n    B1b --- B1b1[\"Include 2&lt;br\/>subset=[2,2]&lt;br\/>target=1, index=4\"]\n    B1b --- B1b2[\"Exclude 2&lt;br\/>subset=[2]&lt;br\/>target=3, index=4\"]\n    \n    B2a --- B2a1[\"Include 2&lt;br\/>subset=[2,2]&lt;br\/>target=1, index=4\"]\n    B2a --- B2a2[\"Exclude 2&lt;br\/>subset=[2]&lt;br\/>target=3, index=4\"]\n    \n    B2b --- B2b1[\"Include 2&lt;br\/>subset=[2]&lt;br\/>target=3, index=4\"]\n    B2b --- B2b2[\"Exclude 2&lt;br\/>subset=[]&lt;br\/>target=5, index=4\"]\n    \n    %% Level 4 results\n    A1b1 --- Success2[\"target=0&lt;br\/>\u2705 Add (1,2,2) to set&lt;br\/>(Duplicate - ignored)\"]\n    A2a1 --- Success3[\"target=0&lt;br\/>\u2705 Add (1,2,2) to set&lt;br\/>(Duplicate - ignored)\"]\n    \n    B1a1 --- Fail1[\"target=-1&lt;br\/>\u274c Return (pruning)\"]\n    \n    %% Continue with remaining paths that lead to [5]\n    A2b2 --- A2b2a[\"Include 5&lt;br\/>subset=[1,5]&lt;br\/>target=-1, index=5\"]\n    A2b2 --- A2b2b[\"Exclude 5&lt;br\/>subset=[1]&lt;br\/>index=5\"]\n    \n    B2b2 --- B2b2a[\"Include 5&lt;br\/>subset=[5]&lt;br\/>target=0, index=5\"]\n    B2b2 --- B2b2b[\"Exclude 5&lt;br\/>subset=[]&lt;br\/>index=5\"]\n    \n    A2b2a --- Fail2[\"target=-1&lt;br\/>\u274c Return (pruning)\"]\n    B2b2a --- Success4[\"target=0&lt;br\/>\u2705 Add (5) to set\"]\n    \n    %% Final result\n    Success1 --- Result[\"Final: {(1,2,2), (5)}&lt;br\/>Convert to [[1,2,2], [5]]\"]\n    Success4 --- Result\n\n    %% Styling\n    style Success1 fill:#90EE90\n    style Success2 fill:#90EE90\n    style Success3 fill:#90EE90\n    style Success4 fill:#90EE90\n    style Result fill:#90EE90\n    \n    style Fail1 fill:#FFB6C1\n    style Fail2 fill:#FFB6C1\n<\/pre><\/div>\n\n\n\n<p>Click <strong><a href=\"https:\/\/mermaid.live\/edit#pako:eNqtl99u2jAUxl_F8lQJpNBhJ6EkGpNK_0iTdtXuatALhxiIFhKUOF071Mvd7RG2l-uTzDixMQFD05ZK0MTOd34-_s4xrOAkDSn04Swjyzn4djlOAH_dpCkbjWFAJj9Yxt9aozsLdC3gtj8F2cfPE5KEUUgYzQcjZGHx596JIUayGWUDdwzvSqny_eQEfKX3NAZdH0RJSB8GXE3JDNAmLOh0OuCcB_-STOIipAAJ3bwIcq47QlthHKtSQyqe0hhyjauHfRrbpLsSNWQEplm6AIpHrgDpK8DlQ-clPtL48Ta_hbfCYxkeq_CVBtb48UtygI8sQCXj0AKGZe7MC9jGt3eDVwpm_P3pN9Ljkl5kTpLjfalHVe7JoeTX0t-V4e1N-qVOYN4A0ybaRxdxeAm42nrS3D_aAqRK0NRBR_EP78AQVeYx49fzj3ZDKxUzvsGDR_EP0-PKuKSp9zV2qRE0dL8R3QYZzYuY5dKcRES4LSYTmufrMpVOFrrPf3-D8zAELWH1NmAp4FFr4tza0uLoNbXiaLWilHDzanHqXJhI_7-Va6P0LlyBrKhXNHadSuk0bu51pmFlBP6JDlVbjaqDdgU1KTOWsXB3wQJZv6h5G9CplA5u2gh2mCo7DDF5G9NG5x2YAtkrGh-2OpFSaXrgOqaW49RbToD0noNf1nPEUOuyWMbRhHdZ0AHRLEkzGrb1Kt1Stt9NWRm71L8mUay1yk75dfD53x9wQ1mRJaC1zIokSmbt3ZxcpAmLkoKCnxGb88wsSLSeCZaEzXPA5oSBmJJwzTZyN4WuzuCt48SttQzXUJyu3jM2Uvqp4u7rGvWnlUnUuXQAx93fVV3dbBsdM8shFJEQtSe42Z4M1cOVYRyjYVzD0cc39DpKSFxZvLwpD1MhfSMGuLCY54NVZT5rLfokonBL3NOMiS2vziNrvfl3Kpjk0xTHiSK4ZY8xX1h5nfMLukGYRnHsf_C6V1ded88EfGyCfWyCY5xQcu4Z1ieJUqrmXF8PexeoPopro9DiPy6jEPosK6gFFzTjJcQv4Wr9JN_AOV3QMfT5vyGdknWq4Dh54o8tSfI9TRfyySwtZnPoT0mc86tiuf7ydhkR_st1oe5mlNsuu0iLhEEf9bpnQgX6K_jArx3vtM9f2PN6Xs_u264FH6HfcfBpD_MbHur3XdS3-08W_CUCo1MbYc_uO94ZRsjFffvpP3u3kFE\" 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>&nbsp;O(2^n) &#8211; We explore 2^n possible combinations in worst case, plus time for set operations<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(k) &#8211; Where k is the number of unique combinations, plus recursion stack space<\/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 trying on all possible outfit combinations and taking photos, then later removing duplicate photos. It&#8217;s straightforward but not the most efficient since we generate duplicates and then remove them.<\/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-smart-duplicate-avoidance\">Solution 2: Optimal Approach (Smart Duplicate Avoidance)<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"9-intuition\">Intuition<\/h3>\n\n\n\n<p>Instead of generating duplicates and removing them later, why not avoid generating them in the first place? The key insight is that after sorting, duplicate elements are adjacent. When we&#8217;re at a position and considering whether to include a number, if it&#8217;s the same as the previous number and we didn&#8217;t include the previous number in our current path, then including the current number would create a duplicate combination. So we skip it! It&#8217;s like having identical items in a bag &#8211; once you decide to skip the first copy of an item at a level, you should skip all remaining copies at that same level.<\/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>Sort the Array<\/strong>: Sort candidates to group duplicate values together.<\/li>\n\n\n\n<li><strong>Use For Loop<\/strong>: Instead of include\/exclude pattern, use a for loop to try each remaining candidate.<\/li>\n\n\n\n<li><strong>Skip Duplicates<\/strong>: If&nbsp;<code>i &gt; index<\/code>&nbsp;and&nbsp;<code>candidates[i] == candidates[i-1]<\/code>, skip this candidate to avoid duplicates.<\/li>\n\n\n\n<li><strong>Early Termination<\/strong>: If&nbsp;<code>candidates[i] &gt; target<\/code>, break the loop (since array is sorted, all remaining elements are also &gt; target).<\/li>\n\n\n\n<li><strong>Recursive Call<\/strong>: Include current candidate and recursively solve for remaining target and remaining candidates.<\/li>\n\n\n\n<li><strong>Backtrack<\/strong>: Remove the candidate after exploring its path.<\/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 backtrack(self, subset, index, target, result, candidates):\n        # Base case: Found a valid combination\n        if target == 0:\n            result.append(subset.copy())  # Add copy to preserve current state\n            return\n        \n        # Try each candidate from current index onwards\n        for i in range(index, len(candidates)):\n            # Skip duplicates: if current element is same as previous and we're not\n            # at the starting position, skip it to avoid duplicate combinations\n            if i &gt; index and candidates[i] == candidates[i - 1]:\n                continue\n            \n            # Early termination: if current candidate exceeds target,\n            # all remaining candidates will also exceed (array is sorted)\n            if candidates[i] &gt; target:\n                break\n            \n            # Include current candidate\n            subset.append(candidates[i])\n            self.backtrack(subset, i + 1, target - candidates[i], result, candidates)\n            \n            # Backtrack: remove the candidate\n            subset.pop()\n\n    def combinationSum2(self, candidates: List[int], target: int) -&gt; List[List[int]]:\n        candidates.sort()  # Sort to enable duplicate skipping and early termination\n        result = []\n        self.backtrack([], 0, target, result, candidates)\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\">backtrack<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">subset<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">index<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">result<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">candidates<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># Base case: Found a valid combination<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> target == <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            result.append(subset.copy())  <\/span><span style=\"color: #6A9955\"># Add copy to preserve current 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\"># Try each candidate from current index onwards<\/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\">(index, <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(candidates)):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># Skip duplicates: if current element is same as previous and we&#39;re not<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># at the starting position, skip it to avoid duplicate combinations<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> i &gt; index <\/span><span style=\"color: #569CD6\">and<\/span><span style=\"color: #D4D4D4\"> candidates[i] == candidates[i - <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">continue<\/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\"># Early termination: if current candidate exceeds target,<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #6A9955\"># all remaining candidates will also exceed (array is sorted)<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> candidates[i] &gt; target:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">break<\/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\"># Include current candidate<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            subset.append(candidates[i])<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #569CD6\">self<\/span><span style=\"color: #D4D4D4\">.backtrack(subset, i + <\/span><span style=\"color: #B5CEA8\">1<\/span><span style=\"color: #D4D4D4\">, target - candidates[i], result, candidates)<\/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 the candidate<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            subset.pop()<\/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\">combinationSum2<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">candidates<\/span><span style=\"color: #D4D4D4\">: List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">], <\/span><span style=\"color: #9CDCFE\">target<\/span><span style=\"color: #D4D4D4\">: <\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">) -&gt; List[List[<\/span><span style=\"color: #4EC9B0\">int<\/span><span style=\"color: #D4D4D4\">]]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        candidates.sort()  <\/span><span style=\"color: #6A9955\"># Sort to enable duplicate skipping and early termination<\/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\">.backtrack([], <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, target, result, candidates)<\/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 cleverly avoids generating duplicate combinations by skipping duplicate elements at each level of recursion. The condition&nbsp;<code>if i &gt; index and candidates[i] == candidates[i - 1]: continue<\/code>&nbsp;ensures that we only use the first occurrence of any duplicate value at each recursion level. The for loop approach naturally handles the choice of which elements to include, and the early termination (<code>if candidates[i] &gt; target: break<\/code>) saves time by stopping as soon as we encounter an element too large for the remaining target.<\/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[\"backtrack([], 0, 5)&lt;br\/>candidates=[1,2,2,2,5]\"]\n    \n    %% Level 0 branches\n    Root --- A[\"i=0: Try 1&lt;br\/>subset=[1]\"]\n    Root --- B[\"i=1: Try 2&lt;br\/>subset=[2]\"]\n    Root --- C[\"i=2,3: Skip&lt;br\/>(duplicates)\"]\n    Root --- D[\"i=4: Try 5&lt;br\/>subset=[5]\"]\n    \n    %% Branch A: [1] - Level 1\n    A --- A1[\"i=1: Try 2&lt;br\/>subset=[1,2]\"]\n    A --- A2[\"i=2,3: Skip&lt;br\/>(duplicates)\"]\n    A --- A3[\"i=4: Break&lt;br\/>(5 > 4)\"]\n    \n    %% Branch A1: [1,2] - Level 2  \n    A1 --- A1a[\"i=2: Try 2&lt;br\/>subset=[1,2,2]\"]\n    A1 --- A1b[\"i=3: Skip&lt;br\/>(duplicate)\"]\n    A1 --- A1c[\"i=4: Break&lt;br\/>(5 > 2)\"]\n    \n    %% Branch A1a: [1,2,2] - Level 3\n    A1a --- Success1[\"target=0&lt;br\/>\u2705 [1,2,2]\"]\n    \n    %% Branch B: [2] - Level 1\n    B --- B1[\"i=2: Skip&lt;br\/>(duplicate)\"]\n    B --- B2[\"i=3: Try 2&lt;br\/>subset=[2,2]\"]\n    B --- B3[\"i=4: Break&lt;br\/>(5 > 3)\"]\n    \n    %% Branch B2: [2,2] - Level 2\n    B2 --- B2a[\"i=4: Break&lt;br\/>(5 > 1)\"]\n    \n    %% Branch D: [5] - Level 1\n    D --- Success2[\"target=0&lt;br\/>\u2705 [5]\"]\n    \n    %% Final Result\n    Success1 --- Result[\"Final: [[1,2,2], [5]]\"]\n    Success2 --- Result\n\n    %% Styling\n    style Success1 fill:#90EE90\n    style Success2 fill:#90EE90  \n    style Result fill:#90EE90\n    \n    style A2 fill:#FFE4B5\n    style A1b fill:#FFE4B5\n    style B1 fill:#FFE4B5\n    style C fill:#FFE4B5\n    \n    style A3 fill:#FFB6C1\n    style A1c fill:#FFB6C1\n    style B3 fill:#FFB6C1\n    style B2a fill:#FFB6C1\n<\/pre><\/div>\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>&nbsp;O(2^n) &#8211; Still explores exponential combinations, but with smart pruning<\/li>\n\n\n\n<li><strong>Space Complexity:<\/strong>&nbsp;O(k) &#8211; Where k is the number of unique valid combinations, plus recursion stack<\/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 being smart about trying outfit combinations &#8211; if you have two identical shirts, and you decide not to wear the first one in a particular combination, you automatically skip the second identical shirt too. This prevents creating duplicate outfits altogether, making it much more efficient.<\/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 (Set)<\/td><td>O(2^n)<\/td><td>O(k)<\/td><td>Medium<\/td><td>Understanding the problem<\/td><\/tr><tr><td>Optimal (Smart Skip)<\/td><td>O(2^n)<\/td><td>O(k)<\/td><td>Hard<\/td><td>Production code<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>The&nbsp;<strong>optimal approach<\/strong>&nbsp;is generally preferred because it avoids generating duplicates in the first place, making it more efficient both in terms of time and space. The brute force approach is easier to understand initially but less elegant.<\/p>\n\n\n\n<p>The key insight for Combination Sum II is handling duplicates intelligently. The optimal solution demonstrates a beautiful technique for avoiding duplicate combinations in backtracking problems &#8211; a pattern that appears in many similar problems like Subsets II and Permutations II!<\/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>Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in&nbsp;candidates&nbsp;where the candidate numbers sum to&nbsp;target. Each number in&nbsp;candidates&nbsp;may only be used&nbsp;once&nbsp;in the combination. Here&#8217;s the [Problem Link] to begin with. Note:&nbsp;The solution set must not contain duplicate combinations. Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8Output: [[1,1,6],[1,2,5],[1,7],[2,6]]<\/p>\n","protected":false},"author":1,"featured_media":755,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[32,18],"class_list":{"0":"post-751","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-expert","9":"tag-advance-recursion","10":"tag-hard"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/07\/combination-sum-2-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\/751","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=751"}],"version-history":[{"count":5,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/751\/revisions"}],"predecessor-version":[{"id":758,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/751\/revisions\/758"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/755"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=751"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}