# 1354. Construct Target Array With Multiple Sums

Given an array of integers `target`. From a starting array, `A` consisting of all 1's, you may perform the following procedure :

* let `x` be the sum of all elements currently in your array.
* choose index `i`, such that `0 <= i < target.size` and set the value of `A` at index `i` to `x`.
* You may repeat this procedure as many times as needed.

Return True if it is possible to construct the `target` array from `A` otherwise return False.

**Example 1:**

```
Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1] 
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done
```

**Example 2:**

```
Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].
```

**Example 3:**

```
Input: target = [8,5]
Output: true
```

**Constraints:**

* `N == target.length`
* `1 <= target.length <= 5 * 10^4`
* `1 <= target[i] <= 10^9`

从全1数组开始，每步计算数组的和并用该和将一个元素值替换，问最后能否变成给定的target数组。此题和780 Reach Points极为类似，倒着从target数组开始，被替换的元素一定是当前最大的元素并且它的值是上一步的数组和，再根据当前和就可以算出该元素替换前的值是多少，依次类推看最后能否退到1。对于像\[100000000,1]的，最大值是其它元素很多倍的，取mod来进一步压缩时间。

参考自[这](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/510214/C%252B%252B-Reaching-Points-Work-Backwards)。

```cpp
class Solution {
public:
    bool isPossible(vector<int>& target) {
        long s = accumulate(target.begin(), target.end(), (long) 0);
        priority_queue<int> pq(target.begin(), target.end());
        while (true) {
            auto cur = pq.top(); pq.pop();
            if (cur == 1) return true;
            auto rest = s - cur;
            if (cur <= rest) return false;
            auto pre = cur % rest;
            pq.push(pre);
            s = pre + rest;
        }
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/1354.-construct-target-array-with-multiple-sums.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.