Optimize Financial Record Selection
Intuit empowers millions of consumers and small businesses to manage their financial lives with confidence. A key aspect of financial management involves optimizing benefits, such as maximizing tax deductions or credits. Imagine a scenario where users are selecting from a pool of financial records (e.g., expenses, donations, investments) to achieve a specific financial goal. However, various regulations or personal rules impose limits on how many items of certain categories can be claimed or utilized.
This problem challenges you to develop an algorithm that identifies all possible combinations of financial records that meet an exact target benefit, while strictly adhering to category-specific count limitations.
Given a list of FinancialRecord objects, a targetBenefit value, and a map of categoryLimits (specifying the maximum count for each category), your task is to find all unique combinations of FinancialRecord objects whose total value sums up to exactly targetBenefit, while respecting the categoryLimits. Each FinancialRecord can be used at most once in any combination.
Input:
financialRecords: An array of FinancialRecord objects. Each object has two properties: value: number (the monetary value of the record) and category: string (the type of the record, e.g., 'DEDUCTION_A', 'CREDIT_B').targetBenefit: A number representing the exact total value that the chosen combination of records must sum up to.categoryLimits: An object (acting as a hash map) where keys are string (category names) and values are number (the maximum allowed count for records of that category within a combination).Output:
FinancialRecord objects. Each inner array represents a unique combination of records that satisfies both the targetBenefit sum and all categoryLimits. The order of records within a combination does not matter, and the order of combinations in the output array does not matter.financialRecords is empty, return an empty array [].values in financialRecords and targetBenefit are positive integers.financialRecords is not found as a key in categoryLimits, assume there is no count limit for that category (i.e., effectively an infinite limit).financialRecords contains multiple records with identical value and category (e.g., two different 'Charity' records both valued at 50), these are distinct items. However, to ensure unique combinations of values in the output, you should sort the input financialRecords and implement logic to skip identical adjacent elements during backtracking (similar to 'Combination Sum II' problems). This means [{value: 10, category: 'A'}, {value: 20, category: 'B'}] and [{value: 20, category: 'B'}, {value: 10, category: 'A'}] are considered the same combination, and if financialRecords had two {value: 10, category: 'A'} items, only one combination [{value: 10, category: 'A'}, ...] using one of them would be considered if the other is skipped to avoid duplicates.Examples
Example 1
Input:
financialRecords = [{value: 10, category: 'DEDUCTION_A'}, {value: 5, category: 'CREDIT_B'}, {value: 15, category: 'DEDUCTION_A'}, {value: 20, category: 'CREDIT_B'}], targetBenefit = 25, categoryLimits = {'DEDUCTION_A': 2, 'CREDIT_B': 1}
Output:
[[{"value":10,"category":"DEDUCTION_A"},{"value":15,"category":"DEDUCTION_A"}]]
Note:
After sorting the input (e.g., by value then category), the records are: [{v:5, c:'CREDIT_B'}, {v:10, c:'DEDUCTION_A'}, {v:15, c:'DEDUCTION_A'}, {v:20, c:'CREDIT_B'}].
[{v:10, c:'DEDUCTION_A'}, {v:15, c:'DEDUCTION_A'}] sums to 25. 'DEDUCTION_A' count is 2 (within limit), 'CREDIT_B' count is 0 (within limit). This is a valid combination.[{v:5, c:'CREDIT_B'}, {v:20, c:'CREDIT_B'}] sums to 25. However, the 'CREDIT_B' count would be 2, which exceeds its limit of 1. Thus, it's not a valid combination.Example 2
Input:
financialRecords = [{value: 7, category: 'EXPENSE'}, {value: 3, category: 'EXPENSE'}, {value: 5, category: 'INCOME'}, {value: 7, category: 'EXPENSE'}], targetBenefit = 10, categoryLimits = {'EXPENSE': 1, 'INCOME': 1}
Output:
[[{"value":3,"category":"EXPENSE"},{"value":7,"category":"INCOME"}]]
Note:
Sorted records: [{v:3, c:'EXPENSE'}, {v:5, c:'INCOME'}, {v:7, c:'EXPENSE'}, {v:7, c:'EXPENSE'}].
[{v:3, c:'EXPENSE'}, {v:7, c:'INCOME'}] sums to 10. 'EXPENSE' count is 1 (within limit), 'INCOME' count is 1 (within limit). Valid.[{v:7, c:'EXPENSE'}, {v:3, c:'EXPENSE'}] would exceed 'EXPENSE' limit (count 2 > 1).{value: 7, category: 'EXPENSE'} are treated as distinct items in the input, but due to the uniqueness requirement and sorting, only distinct combinations of values are returned. The categoryLimits further restrict choices.Example 3
Input:
financialRecords = [{value: 100, category: 'INVESTMENT'}, {value: 50, category: 'LOAN'}, {value: 200, category: 'INVESTMENT'}], targetBenefit = 150, categoryLimits = {'INVESTMENT': 1, 'LOAN': 1}
Output:
[[{"value":50,"category":"LOAN"},{"value":100,"category":"INVESTMENT"}]]
Note:
Sorted records: [{v:50, c:'LOAN'}, {v:100, c:'INVESTMENT'}, {v:200, c:'INVESTMENT'}].
[{v:50, c:'LOAN'}, {v:100, c:'INVESTMENT'}] sums to 150. 'LOAN' count is 1 (within limit), 'INVESTMENT' count is 1 (within limit). This is a valid combination.Constraints
1 <= financialRecords.length <= 201 <= financialRecords[i].value <= 1000financialRecords[i].category consists of uppercase English letters and underscores.1 <= targetBenefit <= 20000categoryLimits keys are valid categories, values 1 <= limit <= financialRecords.length.values and targetBenefit are positive integers.targetBenefit sum and the dynamic categoryLimits into the search logic.FinancialRecord entries (by value and category) in the input to ensure only unique combinations of values are present in the final output.Loading editor...