Back to Problems

Combination Sum

Medium
backtracking

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.

Key insight: Unlike regular combinations, the same element CAN be used multiple times. When exploring candidates[i], we can use it again (stay at i) or move to the next candidate (i+1).

Example 1

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2 + 2 + 3 = 7, 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: Multiple ways to reach 8 using the candidates, with repetition allowed.

Example 3

Input: candidates = [2], target = 1
Output: []
Explanation: No combination of 2s can sum to 1.

Constraints

  • •1 <= candidates.length <= 30
  • •2 <= candidates[i] <= 40
  • •All elements of candidates are distinct
  • •1 <= target <= 40
Show Hints (4)
Hint 1: This is similar to combinations, but you can reuse elements.
Hint 2: When you pick candidates[i], you can pick it again OR move to candidates[i+1].
Hint 3: Track the remaining target. When it becomes 0, you found a valid combination.
Hint 4: If the remaining target becomes negative, backtrack - this path cannot work.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?