Combination Sum
Updated
Problem statement
Given distinct positive denominations candidates and a positive integer target, return every different combination of denominations whose sum equals target. Each denomination may be used any number of times.
Sort the values inside each combination in nondecreasing order, and list the combinations in lexicographic order. Combinations that differ only in the order of their values count as one. Return an empty list when no combination exists.
The target is in cents and can be any amount up to 100, where 100 cents is one dollar.
Function
combinationSum(candidates: int[], target: int) → List<List<Integer>>Examples
Example 1
candidates = [2,3,6,7]target = 7return = [[2,2,3],[7]]Both [2,2,3] and [7] add up to the target, and no other combination does. Reordering [2,2,3] does not make a new combination.
Example 2
candidates = [2,3,5]target = 8return = [[2,2,2,2],[2,3,3],[3,5]]Only [2,2,2,2], [2,3,3] and [3,5] add up to the target. Each list is sorted, and the lists are in lexicographic order.
Constraints
1 <= candidates.length <= 61 <= candidates[i] <= 100- All candidate denominations are distinct.
1 <= target <= 100- At most 300 different combinations satisfy an input.
More BAMTECH Media Phone Screen questions
Similar questions at other companies
- Sort by Checking PermutationsMercor · PHONE SCREENMercor interview questions
- Largest Number Below N from Reusable DigitsByteDance · PHONE SCREENByteDance interview questions
- SubsetsTemu · PHONE SCREENTemu interview questions
- Optimal Account BalancingPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- PermutationsEPAM · PHONE SCREENEPAM interview questions
- Word Break IIAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Optimal Account BalancingSalesforce · PHONE SCREENSalesforce interview questions
- Find GPU Capacity and Drain a NodeTogether AI · PHONE SCREEN
- Word Break IIBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- All Subsets with a Given SumApple · PHONE SCREENApple interview questions