Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

100. Combination Sum

MediumDay 29 of 60Recursion & Backtracking

Given an array of distinct positive integers candidates and a positive target, return all unique combinations of candidates that add up to target. The same number may be used any number of times. Two combinations are the same if they use each number the same number of times, regardless of order. Return them in any order.

Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
2 + 2 + 3 = 7 and 7 = 7. No other combination works.
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Constraints
  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • All candidates are distinct
  • 1 <= target <= 40
Hints
Frequently asked at: Amazon, Apple, Adobe, Uber
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min