Generate Target Expressions with Addition and Multiplication

Given an ordered array of digits digits and an integer target, insert only + or * between adjacent digits. You may also add parentheses to change the evaluation order. The relative order of digits must not change, and digit concatenation is not allowed. Return every distinct expression whose value is exactly target. Expressions must follow normal operator precedence: * has higher precedence than +; add parentheses only when they are necessary to override that default precedence. For example, for digits = [2, 3, 4] and target = 14, valid expressions include: 2*(3+4) 2+3*4 Input Format n target d1 d2 ... dn n is the number of digits. target is the target integer. The second line contains n integers d1 ... dn. Output Format Print all valid expressions in lexicographical order, one per line. If none exists, print: NONE Constraints 1 <= n <= 8 0 <= di <= 9 0 <= target <= 10^9 The number of answers can be exponential; the test data guarantees that the total output size is manageable. Example Input 3 14 2 3 4 Output 2*(3+4) 2+3*4