This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu
The Combination Sum problem is a classic backtracking question from LeetCode (#39).
We are given:
- An array of positive integers
candidates(no duplicates inside). - A target integer
target.
We must return all unique combinations where the chosen numbers add up exactly to target.
Numbers can be reused unlimited times.
🎯 Example
candidates = [2, 3, 6, 7], target = 7
Output:
[
[2, 2, 3],
[7]
]
Why?
-
[2, 2, 3]→ adds to 7 -
[7]→ also adds to 7 - No other valid combinations exist.
🧠Approach – Backtracking (DFS)
This is a search problem. Think of it like exploring all possible "paths" of numbers until:
- The sum equals
target→ ✅ valid combination - The sum exceeds
target→ ❌ invalid, stop - We’ve tried all numbers → ❌ stop
We use DFS + backtracking:
- Start at index
0with an empty path[]and total0. - At each step:
- Either include the current candidate (stay on same index since we can reuse it).
- Or skip it and move to the next index.
- Whenever
total === target, we push a copy of the path into results. - Backtrack by popping out the last choice and continue exploring.
- Whenever
âś… Code (JavaScript)
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let res = [];
const dfs = (i, curr, total) => {
if (total === target) {
res.push([...curr]); // store valid combination
return;
}
if (i >= candidates.length || total > target) {
return; // stop exploring
}
// 1. Choose the current number
curr.push(candidates[i]);
dfs(i, curr, total + candidates[i]); // stay on i since reuse is allowed
curr.pop(); // backtrack
// 2. Skip the current number
dfs(i + 1, curr, total);
};
dfs(0, [], 0);
return res;
};
⏱️ Time and Space Complexity
Let’s analyze:
Time Complexity
- In the worst case, each number can be chosen multiple times until we exceed the target.
- The height of the recursion tree is at most
target / min(candidates). - At each level, we branch into choose or skip → about
2^nstyle growth. - Worst-case complexity:
O(2^n * t)
where
tis the target (because we keep adding numbers until reaching it).
In practice, it runs much faster due to pruning (total > target).
Space Complexity
- O(target/min(candidates)) for the recursion depth (stack space).
- Plus storage for results, which could be exponential in the number of combinations.
🚀 Key Takeaways
- Backtracking is perfect when we need all possible solutions.
-
The trick is in branching:
- Reuse the current candidate →
dfs(i, ...) - Skip it →
dfs(i+1, ...)
- Reuse the current candidate →
The stopping condition
if (i >= candidates.length || total > target)prevents infinite recursion.
This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu | Sciencx (2025-08-30T09:31:41+00:00) Leetcode – 39. Combination Sum. Retrieved from https://www.scien.cx/2025/08/30/leetcode-39-combination-sum/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.