Combination Sum🦂

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.
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Input: candidates = [2], target = 1
Output: []
  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • All elements of candidates are distinct.
  • 1 <= target <= 500

Solution

So if you look at the question we have to generate every possible subsequence which can be generated from the given array and not just every possible subsequence, as the question states that any digit can be used multiple times as well. So if I have been given an array {1} and a target 10 then there will be a combination sum {1,1,1,1,1,1,1,1,1,1} even if the array has only 1 element in it but I'm allowed to use the same number as many times as I want.

Code

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store