{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicgdyq2rgm5c43t6bhxexwtqu2iin6qibvz5f3pv5eevhegnd2cne",
    "uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3moiaabb5y3t2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreibwm37z2vblfz2btympqa75xx6qgrpt3dy7veezg6vo5wn4yjxyii"
    },
    "mimeType": "image/webp",
    "size": 52284
  },
  "path": "/jaspreet_singh_86ae1740ac/combination-sum-backtracking-31ip",
  "publishedAt": "2026-06-17T11:24:11.000Z",
  "site": "https://dev.to",
  "tags": [
    "algorithms",
    "computerscience",
    "interview",
    "leetcode",
    "leetcode.com"
  ],
  "textContent": "\nleetcode.com\n\n\n##  Problem Statement\n\nGiven an array of distinct integers `candidates` and a target value `target`, return all unique combinations where the chosen numbers sum to the target.\n\nA number may be chosen **unlimited times**.\n\n##  Brute Force Intuition\n\nFor every element, we have two choices:\n\n\n\n    Pick it\n    Skip it\n\n\nIf we pick an element, we can pick it again because repetitions are allowed.\n\nWe keep exploring all possible combinations until:\n\n  * Target becomes `0` → Valid combination\n  * Target becomes negative → Invalid path\n\n\n\n##  Pattern Recognition\n\nWhenever you see:\n\n  * Generate all possible combinations\n  * Target Sum\n  * Unlimited usage of elements\n\n\n\nThink:\n\n**Backtracking + Pick / Not Pick**\n\n##  Key Observation\n\nUnlike Subsets:\n\n\n\n    After picking an element,\n    we stay at the same index.\n\n\nWhy?\n\nBecause the same element can be used multiple times.\n\nExample:\n\n\n\n    candidates = [2,3,6,7]\n    target = 7\n\n\nTo form:\n\n\n\n    [2,2,3]\n\n\nwe must be able to pick `2` repeatedly.\n\n##  Optimal Java Solution\n\n\n    import java.util.*;\n\n    class Solution {\n\n        public List<List<Integer>> combinationSum(int[] candidates, int target) {\n\n            List<List<Integer>> ans = new ArrayList<>();\n\n            helper(0, candidates, target, ans, new ArrayList<>());\n\n            return ans;\n        }\n\n        private void helper(int index,\n                            int[] candidates,\n                            int target,\n                            List<List<Integer>> ans,\n                            List<Integer> ds) {\n\n            if (target == 0) {\n                ans.add(new ArrayList<>(ds));\n                return;\n            }\n\n            if (index == candidates.length) {\n                return;\n            }\n\n            // Pick\n            if (candidates[index] <= target) {\n\n                ds.add(candidates[index]);\n\n                helper(index,\n                       candidates,\n                       target - candidates[index],\n                       ans,\n                       ds);\n\n                ds.remove(ds.size() - 1);\n            }\n\n            // Not Pick\n            helper(index + 1,\n                   candidates,\n                   target,\n                   ans,\n                   ds);\n        }\n    }\n\n\n##  Dry Run\n\n###  Input\n\n\n    candidates = [2,3,6,7]\n    target = 7\n\n\n###  Recursion Tree\n\n\n    7\n\n    Pick 2\n    |\n    5\n\n    Pick 2\n    |\n    3\n\n    Pick 2\n    |\n    1 (Invalid)\n\n    Backtrack\n\n    Pick 3\n    |\n    0 ✅\n\n\nCombination:\n\n\n\n    [2,2,3]\n\n\nAnother path:\n\n\n\n    Pick 7\n    |\n    0 ✅\n\n\nCombination:\n\n\n\n    [7]\n\n\n###  Output\n\n\n    [\n     [2,2,3],\n     [7]\n    ]\n\n\n##  Why Staying on Same Index Works?\n\nWhen we pick:\n\n\n\n    candidates[index]\n\n\nwe call:\n\n\n\n    helper(index, ...)\n\n\ninstead of:\n\n\n\n    helper(index + 1, ...)\n\n\nThis allows:\n\n\n\n    2 → 2 → 2\n\n\nor any number of repeated selections.\n\nWithout this, each number could be used only once.\n\n##  Complexity Analysis\n\nMetric | Complexity\n---|---\nTime Complexity | O(2^T) (Exponential)\nSpace Complexity | O(T)\n\nWhere:\n\n\n\n    T = Target\n\n\nRecursion depth can grow up to target in worst case.\n\n##  Interview One-Liner\n\n> Use backtracking with Pick / Not Pick. When picking an element, stay at the same index because elements can be reused multiple times.\n\n##  Pattern Learned\n\n\n    Target Sum\n    +\n    Generate All Combinations\n    +\n    Unlimited Usage Allowed\n\n    => Backtracking\n    => Pick / Not Pick\n    => Stay on Same Index After Pick\n\n\n###  Similar Problems\n\n  * Combination Sum\n  * Coin Change (Generate Ways)\n  * Unbounded Knapsack\n  * Rod Cutting\n  * Integer Break\n\n",
  "title": "Combination Sum | Backtracking"
}