Combination Sum
Medium · Backtracking
You are given a list of distinct positive integers and a target value. Find every combination of numbers from the list that adds up exactly to the target, where you may reuse each number as many times as needed. Return all such combinations, without including two combinations that contain the same multiset of numbers in a different order.
Examples
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Why: 2+2+3=7 and 7=7 are the only ways to reach 7 using these numbers with repetition allowed.Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Why: These are the only combinations of 2, 3, and 5 (with repeats) that sum to 8.Input: candidates = [2], target = 1
Output: []
Why: No combination of 2's can ever sum to 1.Constraints
1 <= candidates.length <= 30, 2 <= candidates[i] <= 40, all candidates are distinct, 1 <= target <= 40
Practise it by voice
Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.
This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Combination Sum. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.