Combination Sum With Unlimited Reuse
Updated
Problem statement
You are given an array of distinct integers nums and a target k. Find every combination of numbers from nums that adds up to exactly k. Each number may be used any number of times, including not at all.
Two combinations are the same if they use each number the same number of times, so [2, 3] and [3, 2] count once.
Return the combinations in this order:
- Write each combination with its numbers in ascending order.
- Sort the combinations by comparing their numbers one by one from the left; the first position where two combinations differ decides which comes first.
If no combination adds up to k, return an empty list.
Function
combinationSum(nums: int[], k: int) → List<List<Integer>>Examples
Example 1
nums = [3,5,2]k = 8return = [[2,2,2,2],[2,3,3],[3,5]]Three combinations add up to 8: 2 + 2 + 2 + 2, 2 + 3 + 3 and 3 + 5. Each one is written in ascending order, and the list is sorted: [2, 2, 2, 2] comes before [2, 3, 3] because their second numbers are 2 and 3, and both come before [3, 5], which starts with 3.
[5, 3] and [3, 5] are the same combination, so it appears only once.
Example 2
nums = [4,6]k = 9return = []Every sum of 4s and 6s is even, so 9 can never be reached. The answer is an empty list.
Example 3
nums = [7]k = 14return = [[7,7]]The single number 7 is used twice.
Constraints
1 <= nums.length <= 302 <= nums[i] <= 40- All values in
numsare distinct. 1 <= k <= 40- The answer has at most 150 combinations.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- All Subsequences with Sum KExpedia · ONSITE INTERVIEWExpedia interview questions
- Combination Sum with Reusable ValuesPinterest · PHONE SCREENPinterest interview questions
- All Subsets with a Given SumApple · PHONE SCREENApple interview questions
- Validate a Mahjong Hand PartitionDuolingo · PHONE SCREENDuolingo interview questions
- Count Complete Tic-Tac-Toe GamesDecagon · PHONE SCREEN · ONSITE INTERVIEWDecagon interview questions
- Unique Single-Use Sum CombinationsLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Bounded Combination Sum with Signed CandidatesConfluent · ONSITE INTERVIEWConfluent interview questions
- Spaceship Equipment LoadoutJane Street · ONSITE INTERVIEWJane Street interview questions
- Merge Sort Report with a Noisy ComparatorMercor · ONSITE INTERVIEWMercor interview questions
- K Largest Elements with QuickselectAMD · ONSITE INTERVIEWAMD interview questions