Loading problems...
TL;DR: To solve LeetCode 39, use a backtracking algorithm that builds combinations incrementally, allowing the reuse of elements by maintaining the current index during recursion, and pruning paths that exceed the target sum.
The Combination Sum problem asks us to find all unique combinations of numbers from a given array of distinct integers (candidates) that sum up to a specific target. A critical feature of this problem is that we can use the same number from the candidates array an unlimited number of times. The order of numbers in the output combinations does not matter, but the combinations themselves must be unique.
This is a classic algorithmic challenge often encountered in technical interviews at top tech companies. It tests your ability to manage state space trees and implement recursion effectively.
A naive brute force approach would attempt to generate every possible subset of numbers, including subsets with repeated elements, and check if their sum equals the target. Since we can reuse numbers, the length of a potential combination is theoretically bounded only by target / min(candidates).
To implement this naively, one might write a recursive function that blindly adds numbers to a list until the sum equals or exceeds the target, without a structured strategy to avoid duplicate combinations (permutations of the same set) or optimize the search.
textfunction getAllSubsets(current_path): if sum(current_path) == target: add current_path to results return if sum(current_path) > target: return for number in candidates: // Naively tries every number at every step // This generates [2, 3] and [3, 2] as separate answers getAllSubsets(current_path + [number])
[2, 2, 3] and [2, 3, 2] as different outcomes. Since the problem asks for unique combinations, this requires an expensive post-processing step to filter duplicates.The transition from brute force to the optimal solution relies on defining a strict state-space tree that eliminates duplicates by design rather than by filtering.
The key insight is to control the "search direction." When we decide to include a number candidates[i] in our current combination, we have two valid future choices:
candidates[i] again.candidates[i] and move to candidates[i+1].Crucially, we must never look back. If we are currently considering candidates[i], we cannot add candidates[i-1] to the path. This invariant enforces a non-decreasing order of indices in our construction, guaranteeing that every generated combination is unique (e.g., we will generate [2, 3] but never [3, 2]).
Visual Description: Imagine the algorithm as a traversal of a tree. At the root, we iterate through all candidates. If we pick the first candidate (say, 2), we descend into a child node. From this child node, the valid branches are only the candidate 2 itself and all subsequent candidates (3, 6, 7). The branch for candidate 2 allows repetition. Once we move to the branch for candidate 3, the branch for candidate 2 is no longer available. This structure inherently prunes the possibility of permutations.
Let's trace the execution for candidates = [2, 3, 6, 7], target = 7.
backtrack(start=0, path=[], sum=0)[2], Sum: 2.backtrack(start=0). (Allow reuse of 2)[2]):
[2, 2], Sum: 4.backtrack(start=0).[2, 2]):
[2, 2, 2], Sum: 6.backtrack(start=0).[2, 2, 2]):
[2, 2, 2, 2], Sum: 8.[2, 2, 2, 3], Sum: 9.[2, 2], Sum 4:
i=0 (Value 2). Now i=1 (Value 3).[2, 2, 3], Sum: 7.[2, 2, 3] to results.This systematic depth-first search ensures we find [2, 2, 3] via the path of picking 2, then 2, then 3. We will never find [2, 3, 2] because once we move to index 1 (Value 3), we never iterate back to index 0 (Value 2).
The correctness of this Backtracking approach rests on two pillars:
startIndex and allowing reuse, we explore every possible combination of numbers that could sum to target. The recursion tree covers the entire valid search space.startIndex parameter enforces an ordering constraint. A number at index j can only be followed by numbers at indices k >= j. This effectively sorts the indices used in any combination. Since a set of numbers has exactly one sorted representation, we are guaranteed to generate each unique combination exactly once.cppclass Solution { public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> result; vector<int> currentPath; backtrack(candidates, target, 0, 0, currentPath, result); return result; } private: void backtrack(const vector<int>& candidates, int target, int currentSum, int startIndex, vector<int>& currentPath, vector<vector<int>>& result) { // Base Case: Success if (currentSum == target) { result.push_back(currentPath); return; } // Base Case: Failure (Pruning) if (currentSum > target) { return; } // Recursive Step for (int i = startIndex; i < candidates.size(); ++i) { currentPath.push_back(candidates[i]); // Pass 'i' as startIndex to allow reusing the same element backtrack(candidates, target, currentSum + candidates[i], i, currentPath, result); // Backtrack: remove the last element to explore other possibilities currentPath.pop_back(); } } };
javaimport java.util.ArrayList; import java.util.List; class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); List<Integer> currentPath = new ArrayList<>(); backtrack(candidates, target, 0, 0, currentPath, result); return result; } private void backtrack(int[] candidates, int target, int currentSum, int startIndex, List<Integer> currentPath, List<List<Integer>> result) { // Base Case: Success if (currentSum == target) { // Must create a new ArrayList because currentPath is a reference result.add(new ArrayList<>(currentPath)); return; } // Base Case: Failure (Pruning) if (currentSum > target) { return; } // Recursive Step for (int i = startIndex; i < candidates.length; i++) { currentPath.add(candidates[i]); // Pass 'i' as startIndex to allow reusing the same element backtrack(candidates, target, currentSum + candidates[i], i, currentPath, result); // Backtrack: remove the last element currentPath.remove(currentPath.size() - 1); } } }
pythonfrom typing import List class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: result = [] def backtrack(start_index: int, current_sum: int, current_path: List[int]): # Base Case: Success if current_sum == target: result.append(current_path[:]) # Append a copy of the path return # Base Case: Failure (Pruning) if current_sum > target: return # Recursive Step for i in range(start_index, len(candidates)): num = candidates[i] current_path.append(num) # Pass 'i' to allow reusing the same element backtrack(i, current_sum + num, current_path) # Backtrack current_path.pop() backtrack(0, 0, []) return result
Let be the number of candidates, be the target value, and be the minimum value in candidates.
Time Complexity:
The Backtracking - Combination Sum pattern is highly transferable. Understanding how to manipulate the startIndex and recursion logic allows you to solve variations efficiently:
i + 1 instead of i in the recursive call, along with logic to skip duplicate candidates in the sorted array.Why does my solution contain duplicates like [2, 3] and [3, 2]?
0 in the recursive call (e.g., backtrack(0, ...)).i (the current loop index) as the new startIndex.Why am I getting a StackOverflowError?
currentSum > target.Space Complexity:
currentPath, which grows linearly with the depth of the recursion.currentSum > target0), the recursion depth would be infinite.Why is my solution changing the result list after I added it?
currentPath reference directly to result without making a copy (Java/Python).currentPath is a mutable object. Backtracking steps modify this object. If you store the reference, all entries in your result will end up empty or identical to the final state.new ArrayList<>(currentPath) in Java or current_path[:] in Python.