> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/1354.-construct-target-array-with-multiple-sums.md).

# 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;
        }
    }
};
```