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 <= 40The Combination Sum problem asks you to find all unique combinations of numbers from a given array that add up to a target value. Each number can be used multiple times, which makes this a classic backtracking problem.
The key idea is to explore possible combinations using a depth‑first search (DFS) approach. At each step, you decide whether to include the current candidate number and recursively continue building the combination. To avoid duplicate results, you typically maintain an index so that recursion only explores the current element and those after it.
During recursion, if the running sum exceeds the target, you prune the search branch. If the sum equals the target, the current combination is recorded as a valid solution. Sorting the candidates beforehand can further help with pruning and cleaner exploration.
Because the algorithm explores combinations recursively, the time complexity is exponential in the worst case, while the space complexity depends on recursion depth and the number of stored combinations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking / DFS | O(2^T) approx., where T relates to target and branching possibilities | O(T) recursion depth + space for result storage |
take U forward
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5void findCombination(int* candidates, int candidatesSize
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Combination Sum is a common interview question, especially for companies like Amazon, Google, and Meta. It tests understanding of recursion, backtracking, and pruning strategies.
The problem statement allows unlimited reuse of each candidate number. This is handled in backtracking by keeping the recursive call on the same index instead of moving to the next index after selecting a number.
A dynamic list (or vector) is typically used to build the current combination during recursion. Recursion with backtracking acts as the main control structure, while arrays or lists store the candidate numbers.
The optimal approach uses backtracking with depth-first search to explore all possible combinations of candidates that sum to the target. By maintaining an index and pruning branches when the sum exceeds the target, we avoid unnecessary exploration.
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.