Combination Sum
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]]
Explanation: 2, 3, and 5 are candidates. All combinations that sum to 8 are listed.
Example 3:
Input: candidates = [2], target = 1
Output: []
Explanation: No combination of 2s can sum to 1.
Examples
Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 + 2 + 3 = 7 and 7 = 7 are the only two combinations that sum to the target.
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: All three unique combinations that sum to 8 using the given candidates.
Example 3
Input: candidates = [2], target = 1
Output: []
Explanation: No combination of 2s can produce a sum of 1.
Constraints
- -1 <= candidates.length <= 30
- -2 <= candidates[i] <= 40
- -All elements of candidates are distinct
- -1 <= target <= 40
Optimal Complexity
Time
O(n^(T/M))
Space
O(T/M)
Practice this problem with an AI interviewer
TechInView conducts a full voice mock interview — the AI asks clarifying questions, evaluates your approach, watches you code, and scores you on 5 dimensions. Just like a real FAANG interview.
Start a free interview