Frontend School

Portfolio Value Combinations

DSA
easy

Portfolio Value Combinations

Easy
Backtracking
Combinations
Recursion

Overview

At Zerodha, helping users build and manage their investment portfolios is central to our mission. A common task for investors is to identify different ways to reach a target portfolio value using available financial instruments. This problem focuses on the algorithmic challenge of finding all unique combinations of instrument values that precisely sum up to a desired target.

What you need to do / Task

Implement a function findPortfolioCombinations that, given a list of unique positive integer instrumentValues and a target positive integer, returns all unique combinations of these instrumentValues that add up to the target. Each instrument value can be used an unlimited number of times within a combination.

Input & output

  • instrumentValues: An array of unique positive integers (number[]) representing the values of available financial instruments.
  • target: A positive integer (number) representing the desired total portfolio value.
  • Returns: A list of lists of numbers (number[][]), where each inner list is a unique combination of instrumentValues that sums to target. The order of numbers within a combination does not matter for uniqueness (e.g., [2,3] is considered the same as [3,2]), but the combination itself must be unique in the final output. Combinations should be sorted internally for consistent output (e.g., [2,2,3] instead of [3,2,2]).

Clarifications

  • All instrumentValues are unique positive integers.
  • The target is a positive integer.
  • If no combination sums up to the target, an empty list [] should be returned.

Examples

1

Example 1

Input:

instrumentValues = [2, 3, 6, 7], target = 7

Output:

[[2,2,3],[7]]

Note:

The combinations that sum to 7 are: [7] and [2, 2, 3]. Note that [3,2,2] is considered the same as [2,2,3] and only one should be present. The output combinations are internally sorted for consistency.

2

Example 2

Input:

instrumentValues = [2, 4], target = 8

Output:

[[2,2,2,2],[2,2,4],[4,4]]

Note:

The combinations that sum to 8 are: [2,2,2,2], [2,2,4], and [4,4]. The output combinations are internally sorted for consistency.

3

Example 3

Input:

instrumentValues = [5], target = 3

Output:

[]

Note:

No combination of 5s can sum up to 3.

Constraints

Constraints & assumptions

  • 1 <= instrumentValues.length <= 30
  • 1 <= instrumentValues[i] <= 100
  • All instrumentValues[i] are unique.
  • 1 <= target <= 500
  • All numbers (including target) are positive integers.

What interviewers evaluate

  • Correctness of the backtracking algorithm to explore all possible combinations.
  • Ability to handle the constraint that instrument values can be used multiple times.
  • Ensuring the uniqueness of combinations in the final result.
  • Code clarity, organization, and adherence to best practices for recursive solutions.

Loading editor...