FastPrepAll Subsequences with Sum K
Problems/All Subsequences with Sum K

All Subsequences with Sum K

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2023 report on an Expedia internship process lists this task in the first of two technical interviews, with a short break between them. That first interview was virtual. It asked for every way to choose some numbers from a list, kept in their original order, so that the chosen numbers add up to a target k.

The report gives no input format, limits, examples or output order. Here, the numbers are positive integers. Picks that use different positions count separately even when the values match. Each answer keeps the input order, and answers are listed by the positions they use. The limits of up to 16 numbers from 1 to 50, k up to 800 and at most 200 answers are our choice.

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

You are given an array nums of positive integers and a target k. A subsequence is what is left after deleting zero or more elements of nums without changing the order of the rest. Return every subsequence whose elements add up to exactly k.

Subsequences that use different positions count as different answers, even if they contain the same values. So the same list of values can appear more than once.

Write each subsequence with its elements in their original order. Return the subsequences in this order:

  • Compare two answers by the positions they use: first by their first positions, then by their second positions, and so on. The answer with the smaller position at the first difference comes first.
  • Because all values are positive, two different answers always differ at some position before either one ends.

If no subsequence adds up to k, return an empty list.

Function

subsequencesWithSumK(nums: int[], k: int) → int[][]

Examples

Example 1

nums = [1,2,2,3]k = 3return = [[1,2],[1,2],[3]]

Three choices of positions add up to 3: positions 0 and 1 (1 + 2), positions 0 and 2 (1 + 2), and position 3 alone. The first two use different positions, so [1, 2] is listed twice.

The order follows the positions: [0, 1] comes before [0, 2] because their second positions are 1 and 2, and both come before [3].

Example 2

nums = [2,3,1,4,1]k = 5return = [[2,3],[3,1,1],[1,4],[4,1]]

The subsequences that add up to 5 use positions [0, 1], [1, 2, 4], [2, 3] and [3, 4], which give [2, 3], [3, 1, 1], [1, 4] and [4, 1].

Each one keeps the input order, so [1, 4] and [4, 1] are different answers. They are listed by their first positions: 0, then 1, then 2, then 3.

Example 3

nums = [5,6]k = 4return = []

Every number is larger than 4, so no subsequence adds up to 4. The answer is an empty list.

Constraints

  • 1 <= nums.length <= 16
  • 1 <= nums[i] <= 50
  • 1 <= k <= 800
  • The answer has at most 200 subsequences.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Combination Sum With Unlimited ReuseMicrosoft · ONSITE INTERVIEWMicrosoft 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

  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[][] subsequencesWithSumK(int[] nums, int k) {
        // Write your code here.
    }
}
Checking account…