You are given an array target of n integers.

Starting from an array arr of size n where every element is 1, you may perform the following operation any number of times:

• Let x be the sum of all current elements in arr.

• Pick an index i and set arr[i] = x.

Your task is to return True if it’s possible to construct target from arr, otherwise return False.

Constraints:

• n == target.length

• $1 \leq$ n $\leq 1000$

• $1 \leq$ target[i] $\leq 10^5$

The straightforward approach starts with an array of all 1’s and replaces one element with the sum of all elements, repeating this process. For example, starting with [1, 1, 1, 1], the sum is 4, and one number is replaced with this sum, leading to arrays like [4, 1, 1, 1], [1, 4, 1, 1], and so on. This process grows exponentially as the number of possible paths increases, making it computationally expensive for larger arrays. The expanding sum makes it hard to predict the correct path, and this approach struggles with large arrays due to its high computational cost and inefficiency.

The optimized approach works in reverse, starting from the target array and moving backward toward an array of all 1’s. This method reduces the number of possibilities by eliminating unnecessary branching. Instead of growing the array toward the target, the algorithm reduces the target by calculating the previous values. At each step, it identifies the largest number in the array and computes the sum of the remaining elements.

Instead of directly subtracting the largest number from the sum, the algorithm uses the modulo operation to find the previous value by computing the largest number modulo the sum of the other elements. This step-by-step reduction mimics working backward through the array, simplifying the array structure. A max heap ensures that the largest number is always processed first. This is crucial, as reducing the largest number drives the process toward convergence. The modulo operation progressively reduces the largest element, avoiding unnecessary branching and computations. The algorithm continues reducing until it reaches an array of all 1’s, confirming the target is achievable, or detects an invalid state, signaling failure. This optimized approach handles larger arrays effectively, reducing the largest number step-by-step and making the process computationally efficient and scalable. By working backward and minimizing the search space through subtraction and modulo, the algorithm ensures a unique path to the target, making it faster and more efficient.

The steps of the algorithm are as follows:

1. Initialize a max-heap and push all elements of the target array into the heap.

2. Calculate the total_sum of the target array.

3. Iterate while the max-heap is not empty:

   1. Pop the largest element from the heap (current_max).

   2. Compute the sum of the remaining elements: remaining_sum = total_sum - current_max.

   3. Check for base cases:

      1. If current_max == 1 or remaining_sum == 1, return True, because we can construct the array.

      2. If remaining_sum == 0, or current_max < remaining_sum, or current_max % remaining_sum == 0, return False — it’s invalid or stuck in an infinite loop.

   4. Simulate the reverse of the operation:

      1. Compute the previous value before current_max was formed: updated_value = current_max % remaining_sum.

      2. Update the total sum: total_sum = remaining_sum + updated_value.

      3. Push updated_value back into the heap.

Let’s look at the following illustration to get a better understanding of the solution: