← 返回 waymo 的题目列表Build an Expression with +, -, * and Parentheses to Reach Target
类型：online_judge
Problem Description
Given an integer array nums and an integer target, insert binary operators +, -, and * between the numbers, and add parentheses in any valid way, to determine whether an expression can evaluate to target.
Requirements:
The numbers must be used in their original input order.
Each number must be used exactly once.
Only +, -, and * are allowed.
Parentheses may be added freely to change the evaluation order.
If such an expression exists, return any valid expression.
If no expression exists, output IMPOSSIBLE.
The original interview first asked about 3 numbers, and the follow-up generalized it to n numbers.
Input Format
n
nums[0] nums[1] ... nums[n-1]
target
Output Format
If an expression exists, print any expression that evaluates to target.
Otherwise, print:
IMPOSSIBLE
Constraints
1 <= n <= 8
-20 <= nums[i] <= 20
-10^9 <= target <= 10^9
Examples
Example 1
Input:
3
2 3 4
14
Output:
(2+(3*4))
Example 2
Input:
3
2 3 4
20
Output:
((2+3)*4)
Example 3
Input:
4
1 2 3 4
21
Output:
((1+2)*(3+4))
Example
Input
3
2 3 4
14
Output
(2+(3*4))