Determine whether a target array can be built from an array of ones by repeatedly replacing one element with the sum of the entire array.
You start with an array of length filled with $1$s. In one move, choose any index and replace that value with the sum of the entire current array.
Given a target array, decide whether it is possible to reach exactly that array from the initial array.
The key challenge is to reason backward from the target state efficiently, since forward simulation can grow very quickly.
target of length $n`.target[i] is a positive integer.true if target can be constructed from an array of ones using the operation described above.false.Example 1
Input
target = [9,3,5]
Output
true
Explanation
One valid construction is [1,1,1] -> [1,1,3] -> [1,3,3] -> [9,3,3] -> [9,3,5].
Example 2
Input
target = [1,1,1,2]
Output
false
Explanation
No sequence of allowed operations can produce this array from all ones.
Example 3
Input
target = [8,5]
Output
true
Explanation
[1,1] -> [1,2] -> [3,2] -> [3,5] -> [8,5].
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.