{"id":9440,"date":"2025-08-18T20:10:10","date_gmt":"2025-08-18T14:40:10","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=9440"},"modified":"2025-10-15T16:35:45","modified_gmt":"2025-10-15T11:05:45","slug":"combination-sum","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/combination-sum\/","title":{"rendered":"Combination Sum"},"content":{"rendered":"\n<!-- Evaluate Reverse Polish Notation 10-->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n      <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n<h1 class=\"wp_blog_main-heading\"><\/h1>\n\n<div class=\"wp_blog_explanation\">\n    <h2>Problem Statement:<\/h2>\n    <p>\n        Given an array of distinct integers <code>candidates<\/code> and a target integer <code>target<\/code>, return a list of all unique combinations of <code>candidates<\/code> where the chosen numbers sum to <code>target<\/code>. You may return the combinations in any order.\n    <\/p>\n\n    <p>\n        The same number may be chosen from <code>candidates<\/code> an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.\n    <\/p>\n    \n    <p>\n       The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input. \n    <\/p>  \n    <p><strong>Example 1:<\/strong><\/p>\n    <p><strong>Input:<\/strong> candidates = [2,3,6,7], target = 7<\/p>\n    <p><strong>Output:<\/strong><code> [[2,2,3],[7]]<\/code><\/p>\n    <p><strong>Explanation:<\/strong> 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.\n    7 is a candidate, and 7 = 7.\n    These are the only two combinations.<\/p>\n\n    <p><strong>Example 2:<\/strong><\/p>\n    <p><strong>Input:<\/strong> candidates = [2,3,5], target = 8<\/p>\n    <p><strong>Output:<\/strong><code> [[2,2,2,2],[2,3,3],[3,5]]<\/code><\/p>\n    \n    <p><strong>Example 3:<\/strong><\/p>\n    <p><strong>Input:<\/strong> candidates = [2], target = 1<\/p>\n    <p><strong>Output:<\/strong><code> output: []<\/code><\/p>\n\n\n    <h2>Constraints:<\/h2>\n    <ul>\n        <li><code>1 <= candidates.length <= 30<\/code><\/li>\n        <li><code>2 <= candidates[i] <= 40<\/code><\/li>\n        <li>All elements of <code>candidates<\/code> are <strong>distinct<\/strong>.<\/li>\n        <li><code>1 <= target <= 40<\/code><\/li>\n    <\/ul>\n\n    <h2>Approach:<\/h2>\n   <ul>\n        <li>Use <code>backtracking<\/code> to explore all <strong>possible combinations of numbers<\/strong> that sum up to the target.<\/li>\n        <li><strong>Start from an index<\/strong> (start) to avoid reusing previous elements in the <code>same path<\/code> (but allow reuse of the current one).<\/li>\n        <li><strong>At each step:<\/strong>\n            <ul>\n                <li>If <code>remainingSum === 0<\/code>, store the current path (valid combination).<\/li>\n                <li>If <code>remainingSum <, 0<\/code>, stop exploring further.<\/li>\n                <li>Otherwise, try each number <strong>starting from start<\/strong>, include it in the path, and recurse with reduced sum.<\/li>\n            <\/ul>\n        <\/li>\n        <li><code>Backtrack<\/code> (remove last element) to explore other possibilities.<\/li>\n    <\/ul> \n\n    <!-- <h2>Time Complexity:<\/h2>\n    <li><p><strong>Time Complexity = O(n \u00d7 n!)<\/strong><\/p><\/li> \n    <h2>Space Complexity:<\/h2>\n    <li><p><strong>Space Complexity = O(n) for recursion + O(n!) output storage.<\/strong><\/p><\/li> -->\n\n<h2>Dry Run<\/h2>\n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\">\n\n  <p><strong>Input:<\/strong> <code>arr = [2, 3, 6, 7], target = 7<\/code><\/p>\n\n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\nStep 0: Start Function combinationSum([2, 3, 6, 7], 7)\n\nInitialize:\nresult = []\npath = []\n\nCall backtrack(7, [], 0)\n\nLoop i = 0 \u2192 arr[0] = 2\npath.push(2) \u2192 path = [2]\nCall backtrack(5, [2], 0)\n\n  Loop i = 0 \u2192 arr[0] = 2\n  path.push(2) \u2192 path = [2, 2]\n  Call backtrack(3, [2, 2], 0)\n\n    Loop i = 0 \u2192 arr[0] = 2\n    path.push(2) \u2192 path = [2, 2, 2]\n    Call backtrack(1, [2, 2, 2], 0)\n      remainingSum > 0 but next choice will exceed \u2192 return\n    path.pop() \u2192 path = [2, 2]\n\n    Loop i = 1 \u2192 arr[1] = 3\n    path.push(3) \u2192 path = [2, 2, 3]\n    Call backtrack(0, [2, 2, 3], 1)\n      remainingSum == 0 \u2192 result.push([2, 2, 3])\n    path.pop() \u2192 path = [2, 2]\n\n  Loop ends\n  path.pop() \u2192 path = [2]\n\n  Loop i = 1 \u2192 arr[1] = 3\n  path.push(3) \u2192 path = [2, 3]\n  Call backtrack(2, [2, 3], 1)\n    further exploration doesn\u2019t hit 0 \u2192 backtrack\n  path.pop() \u2192 path = [2]\n\n  Loop i = 2 \u2192 arr[2] = 6\n  path.push(6) \u2192 path = [2, 6]\n  Call backtrack(-1, [2, 6], 2)\n    remainingSum < 0 \u2192 return\n  path.pop() \u2192 path = [2]\n\n  Loop i = 3 \u2192 arr[3] = 7\n  path.push(7) \u2192 path = [2, 7]\n  Call backtrack(-2, [2, 7], 3)\n    remainingSum < 0 \u2192 return\n  path.pop() \u2192 path = [2]\n\nLoop ends\npath.pop() \u2192 path = []\n\nLoop i = 1 \u2192 arr[1] = 3\npath.push(3) \u2192 path = [3]\nCall backtrack(4, [3], 1)\n\n  Loop i = 1 \u2192 arr[1] = 3\n  path.push(3) \u2192 path = [3, 3]\n  Call backtrack(1, [3, 3], 1)\n    no valid combination \u2192 return\n  path.pop() \u2192 path = [3]\n\n  Loop i = 2 \u2192 arr[2] = 6\n  path.push(6) \u2192 path = [3, 6]\n  Call backtrack(-2, [3, 6], 2)\n    remainingSum < 0 \u2192 return\n  path.pop() \u2192 path = [3]\n\n  Loop i = 3 \u2192 arr[3] = 7\n  path.push(7) \u2192 path = [3, 7]\n  Call backtrack(-3, [3, 7], 3)\n    remainingSum < 0 \u2192 return\n  path.pop() \u2192 path = [3]\n\nLoop ends\npath.pop() \u2192 path = []\n\nLoop i = 2 \u2192 arr[2] = 6\npath.push(6) \u2192 path = [6]\nCall backtrack(1, [6], 2)\n  no valid combination \u2192 return\npath.pop() \u2192 path = []\n\nLoop i = 3 \u2192 arr[3] = 7\npath.push(7) \u2192 path = [7]\nCall backtrack(0, [7], 3)\n  remainingSum == 0 \u2192 result.push([7])\npath.pop() \u2192 path = []\n\nLoop ends\n\nStep 3: End\nReturn result = [[2, 2, 3], [7]]\n  <\/pre>\n\n  <p><strong>Output:<\/strong> \n    <code>[[2, 2, 3], [7]]<\/code>\n  <\/p>\n\n  <p><strong>Explanation:<\/strong> The backtracking algorithm explores all possible combinations by adding numbers repeatedly (reuse is allowed). Only the paths where the sum exactly equals <code>target<\/code> are stored in <code>result<\/code>.<\/p>\n  \n<\/div>\n\n<\/div>\n\n<div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n        <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n        <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n<pre><code class=\"language-javascript\">\nvar combinationSum = function(arr, target) {\n    let result = [];\n    let backtrack = (remainingSum, path, start) => {\n        if(remainingSum === 0) result.push([...path]);\n        if(remainingSum <= 0) return;\n        for(let i=start; i < arr.length; i++){\n            path.push(arr[i]);\n            backtrack(remainingSum-arr[i], path, i);\n            path.pop();\n        }\n\n    }\n    backtrack(target, [], 0);\n    return result;\n};\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n<pre><code class=\"language-python\">\ndef combinationSum(arr, target):\n    result = []\n\n    def backtrack(remainingSum, path, start):\n        if remainingSum == 0:\n            result.append(list(path))\n            return\n        if remainingSum < 0:\n            return\n        for i in range(start, len(arr)):\n            path.append(arr[i])\n            backtrack(remainingSum - arr[i], path, i)\n            path.pop()\n\n    backtrack(target, [], 0)\n    return result\n\n\n# Example\narr = [2, 3, 6, 7]\ntarget = 7\nprint(combinationSum(arr, target))\n\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n<pre><code class=\"language-java\">\nimport java.util.*;\n\nclass Solution {\n    public List<List<Integer>> combinationSum(int[] arr, int target) {\n        List<List<Integer>> result = new ArrayList<>();\n        List<Integer> path = new ArrayList<>();\n\n        backtrack(arr, target, path, 0, result);\n        return result;\n    }\n    private void backtrack(int[] arr, int remainingSum, List<Integer> path, int start, List<List<Integer>> result) {\n        if (remainingSum == 0) {\n            result.add(new ArrayList<>(path));\n            return;\n        }\n        if (remainingSum < 0) return;\n\n        for (int i = start; i < arr.length; i++) {\n            path.add(arr[i]);\n            backtrack(arr, remainingSum - arr[i], path, i, result);\n            path.remove(path.size() - 1);\n        }\n    }\n    public static void main(String[] args) {\n        Solution s = new Solution();\n        int[] arr = {2, 3, 6, 7};\n        int target = 7;\n        List<List<Integer>> ans = s.combinationSum(arr, target);\n\n        for (List<Integer> comb : ans) {\n            System.out.println(comb);\n        }\n    }\n}\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n<pre><code class=\"language-cpp\">\nclass Solution {\npublic:\n    vector<vector<int>> combinationSum(vector<int>& arr, int target) {\n        vector<vector<int>> result;\n        vector<int> path;\n        function<void(int, int)> backtrack = [&](int remainingSum, int start) {\n            if (remainingSum == 0) {\n                result.push_back(path);\n                return;\n            }\n            if (remainingSum < 0) return;\n\n            for (int i = start; i < arr.size(); i++) {\n                path.push_back(arr[i]);\n                backtrack(remainingSum - arr[i], i);\n                path.pop_back();\n            }\n        };\n\n        backtrack(target, 0);\n        return result;\n    }\n};\nint main() {\n    Solution s;\n    vector<int> arr = {2, 3, 6, 7};\n    int target = 7;\n    vector<vector<int>> ans = s.combinationSum(arr, target);\n\n    for (auto &comb : ans) {\n        for (int num : comb) cout << num << \" \";\n        cout << endl;\n    }\n}\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n<pre><code class=\"language-c\">\nvoid backtrack(int arr[], int n, int target, int path[], int pathSize, int start) {\n    if (target == 0) {\n        for (int i = 0; i < pathSize; i++) {\n            printf(\"%d \", path[i]);\n        }\n        printf(\"\\n\");\n        return;\n    }\n    if (target < 0) return;\n\n    for (int i = start; i < n; i++) {\n        path[pathSize] = arr[i];\n        backtrack(arr, n, target - arr[i], path, pathSize + 1, i);\n    }\n}\nint main() {\n    int arr[] = {2, 3, 6, 7};\n    int n = 4, target = 7;\n    int path[100];\n    backtrack(arr, n, target, path, 0, 0);\n    return 0;\n}\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n<pre><code class=\"language-csharp\">\nusing System;\nusing System.Collections.Generic;\nclass Solution {\n    public IList<IList<int>> CombinationSum(int[] arr, int target) {\n        var result = new List<IList<int>>();\n        var path = new List<int>();\n        void Backtrack(int remainingSum, int start) {\n            if (remainingSum == 0) {\n                result.Add(new List<int>(path));\n                return;\n            }\n            if (remainingSum < 0) return;\n\n            for (int i = start; i < arr.Length; i++) {\n                path.Add(arr[i]);\n                Backtrack(remainingSum - arr[i], i);\n                path.RemoveAt(path.Count - 1);\n            }\n        }\n        Backtrack(target, 0);\n        return result;\n    }\n}\nclass Program {\n    static void Main() {\n        var s = new Solution();\n        var arr = new int[] {2, 3, 6, 7};\n        var ans = s.CombinationSum(arr, 7);\n\n        foreach (var comb in ans) {\n            Console.WriteLine(string.Join(\" \", comb));\n        }\n    }\n}\n<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[210,260,176,175,211,811,810,174,172,173],"tags":[],"class_list":["post-9440","post","type-post","status-publish","format-standard","category-algorithms","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-dsa","category-java","category-javascript","category-python"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9440","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=9440"}],"version-history":[{"count":4,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9440\/revisions"}],"predecessor-version":[{"id":10332,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9440\/revisions\/10332"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=9440"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=9440"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=9440"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}