{"id":748,"date":"2025-07-22T13:38:14","date_gmt":"2025-07-22T08:08:14","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=748"},"modified":"2025-07-22T13:38:15","modified_gmt":"2025-07-22T08:08:15","slug":"combination-sum","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/combination-sum\/","title":{"rendered":"Combination Sum | Leetcode 39 | Backtracking Approach"},"content":{"rendered":"\n

Given an array of distinct<\/strong> integers candidates<\/code> and a target integer target<\/code>, return a list of all unique combinations<\/strong> of <\/em>candidates<\/code> where the chosen numbers sum to <\/em>target<\/code>.<\/em> You may return the combinations in any order<\/strong>.<\/p>\n\n\n\n

The same<\/strong> number may be chosen from candidates<\/code> an unlimited number of times<\/strong>. Two combinations are unique if the frequency of at least one of the chosen numbers is different.<\/p>\n\n\n\n

The test cases are generated such that the number of unique combinations that sum up to target<\/code> is less than 150<\/code> combinations for the given input.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> candidates = [2,3,6,7], target = 7
Output:<\/strong> [[2,2,3],[7]]
Explanation:<\/strong>
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> candidates = [2,3,5], target = 8
Output:<\/strong> [[2,2,2,2],[2,3,3],[3,5]]<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> candidates = [2], target = 1
Output:<\/strong> []<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n