FastPrepCombination Sum With Unlimited Reuse
Problems/Combination Sum With Unlimited Reuse

Combination Sum With Unlimited Reuse

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a 2025 internship interview loop for Microsoft's Azure Virtual Desktop team, the second round's coding question was a combination-sum task with unlimited reuse. The task is to find every way to reach a target k from the values of an array.

The report does not describe the array values or the output format. This page assumes the values are distinct and at least 2, treats ways that differ only in order as the same combination, and asks for the combinations in a fixed sorted order so they can be checked. The size limits are also our choice: up to 30 values from 2 to 40, k from 1 to 40, and at most 150 combinations in the answer.

Our version is about 90% the same as the reported question.

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 <= 30
  • 2 <= nums[i] <= 40
  • All values in nums are 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

Interview reports that mention this question

  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public List<List<Integer>> combinationSum(int[] nums, int k) {
        // Write your code here.
    }
}
Checking account…