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 unique if the frequency of at least one of the chosen numbers is different.
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.
Example 1:
Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]] Explanation: 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.
Example 2:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1 Output: []
Constraints:
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates are distinct.1 <= target <= 40Problem Overview: Given an array of distinct integers candidates and a target value, return all unique combinations where numbers sum to the target. Each number can be chosen multiple times, but the result must avoid duplicate combinations.
Approach 1: Backtracking (Exponential time, O(2^T) worst case)
This problem naturally fits backtracking. You build combinations incrementally and explore every valid path whose sum does not exceed the target. Start from an index, add the current number to a running combination, subtract it from the remaining target, and recursively continue. Because numbers can be reused, the recursive call keeps the same index instead of moving forward immediately. When the remaining target becomes 0, you record the current combination. Time complexity is exponential in the worst case because the algorithm explores many candidate combinations, roughly O(2^T) depending on target size and candidate values. Space complexity is O(T) for recursion depth plus output storage.
This approach works well because it prunes invalid paths early. As soon as the running sum exceeds the target, recursion stops for that branch. Sorting the array can help prune faster, but it's not strictly required. Most interview solutions use this pattern with recursion, a temporary list, and a loop that iterates candidates from the current index.
Approach 2: Dynamic Programming (O(n * target * k) time, O(target * k) space)
A dynamic programming formulation builds combinations for every intermediate target from 0 to target. Maintain a DP array where dp[i] stores all combinations that sum to value i. For each candidate number, iterate through target values and extend previously known combinations. If a combination forms i - num, append num to create a valid combination for i. Time complexity is roughly O(n * target * k), where k is the average number of combinations stored per state. Space complexity is also proportional to stored combinations.
Dynamic programming works when you prefer a bottom‑up build rather than recursive exploration. However, the memory overhead grows quickly because every valid combination must be stored in intermediate states.
Recommended for interviews: The backtracking approach is the expected solution. It directly models the search space and demonstrates control over recursion, pruning, and combination generation. Interviewers often ask follow‑ups around pruning, avoiding duplicates, and reasoning about exponential search trees in array-based problems.
This approach uses recursion and backtracking to generate all possible combinations by exploring each candidate. If a candidate is chosen, we explore further with the remaining target reduced by the candidate's value. We use backtracking to remove a candidate and try the next one. This way, we explore all possible combinations using depth-first search.
This C solution uses recursion to explore combinations and backtracks when a target less than zero is reached. If the target is zero, a valid combination is found and added to the result. The helper function findCombination iterates through candidates allowing reuse of the current candidate.
C++
Java
Python
C#
JavaScript
Time Complexity: O(2^T), where T is the target, as it potentially explores every combination of the candidates.
Space Complexity: O(T) for the recursion call stack and the path being explored.
We can use a dynamic programming (DP) approach to solve the Combination Sum problem. We maintain a DP array where each index represents the number of ways to form that particular sum using the candidates. The approach involves iterating through candidates and updating the DP array for each possible sum that can be formed with that candidate.
This C implementation describes the dynamic programming principle by using a combinationSum helper to check for combinations by evaluating the candidates against target sums, updating a dp array to track viable sets.
C++
Java
Python
C#
JavaScript
Time Complexity: Roughly O(T * N), for target T and candidates N.
Space Complexity: O(T) for the dp array itself in context of storage.
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^T), where T is the target, as it potentially explores every combination of the candidates. |
| Dynamic Programming Approach | Time Complexity: Roughly O(T * N), for target T and candidates N. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking | O(2^T) worst case | O(T) recursion + output | Best general solution for generating combinations and interview settings |
| Dynamic Programming | O(n * target * k) | O(target * k) | Useful when building solutions bottom-up or reusing intermediate sums |
L8. Combination Sum | Recursion | Leetcode | C++ | Java • take U forward • 729,835 views views
Watch 9 more video solutions →Practice Combination Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor