#33Recipe Nutrition Formula Builder
A nutrition planning system stores a sequence of digits representing ingredient calorie values. The system wants to explore different ways of combining these digits into numerical calorie quantities. You are given a string calorieDigits containing only digits and an integer calorieTarget.
Insert the binary operators +, -, and * between the digits, or leave some positions unchanged, to construct valid arithmetic expressions whose evaluated result is exactly calorieTarget. Return all valid expressions that evaluate to the target. An ingredient quantity formed from multiple consecutive digits is allowed, but a multi-digit quantity cannot begin with 0. The order of the digits must remain unchanged.
Multiplication follows normal arithmetic precedence, so * is evaluated before + and -. Return the expressions in any order.
Real-World Application
- Personalized meal planning: Generate different combinations of ingredient quantities that reach a prescribed calorie target.
- Diet optimization systems: Explore alternative arithmetic combinations of available nutritional values while respecting the original ingredient sequence.
- Nutrition education software: Demonstrate how different combinations of food quantities can produce the same total calorie value.
Examples
Example 1
Input: calorieDigits = "123"
calorieTarget = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both expressions evaluate to 6.
Example 2
Input: calorieDigits = "232"
calorieTarget = 8
Output: ["2*3+2","2+3*2"]
Explanation: --
Example 3
Input: calorieDigits = "105"
calorieTarget = 5
Output: ["1*0+5","10-5"]
Explanation: --
Constraints
- 1 <= calorieDigits.length <= 10
- calorieDigits contains only digits '0' to '9'.
- -2^31 <= calorieTarget <= 2^31 - 1
- Expressions must preserve the original digit order.
- Operators allowed are +, -, and *.
- Any multi-digit operand formed in an expression cannot have a leading zero.