Dsa
Dynamic Programming
Warm-up
Expense Tracking
You are developing an application to track monthly expenses. You want to know how many unique ways you can split a total amount into categories of expenses without exceeding the total amount for that month. You have a list of expenses and need to calculate this.
Write a function that takes the total amount and a list of expenses, and returns the number of unique combinations that sum up to the total without exceeding it.
Input Format:
- The first line contains an integer total (1 <= total <= 100).
- The second line contains space-separated integers representing the expense categories.
Output Format:
- An integer that represents the number of unique ways to split the total amount.
Example:
Input:
5
1 2 3
Output:
5
Note: The unique combinations that sum to 5 are:
1. 1+1+1+1+1
2. 1+1+1+2
3. 1+2+2
4. 2+3
5. 5
Key concepts
dynamic_programmingarrayscombinatorics
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now