1354. Construct Target Array With Multiple Sums Hard

1/**
2 * [1354] Construct Target Array With Multiple Sums
3 *
4 * You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure :
5 * 
6 * 	let x be the sum of all elements currently in your array.
7 * 	choose index i, such that 0 <= i < n and set the value of arr at index i to x.
8 * 	You may repeat this procedure as many times as needed.
9 * 
10 * Return true if it is possible to construct the target array from arr, otherwise, return false.
11 *  
12 * Example 1:
13 * 
14 * Input: target = [9,3,5]
15 * Output: true
16 * Explanation: Start with arr = [1, 1, 1] 
17 * [1, 1, 1], sum = 3 choose index 1
18 * [1, 3, 1], sum = 5 choose index 2
19 * [1, 3, 5], sum = 9 choose index 0
20 * [9, 3, 5] Done
21 * 
22 * Example 2:
23 * 
24 * Input: target = [1,1,1,2]
25 * Output: false
26 * Explanation: Impossible to create target array from [1,1,1,1].
27 * 
28 * Example 3:
29 * 
30 * Input: target = [8,5]
31 * Output: true
32 * 
33 *  
34 * Constraints:
35 * 
36 * 	n == target.length
37 * 	1 <= n <= 5 * 10^4
38 * 	1 <= target[i] <= 10^9
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/construct-target-array-with-multiple-sums/
44// discuss: https://leetcode.com/problems/construct-target-array-with-multiple-sums/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn is_possible(target: Vec<i32>) -> bool {
50        false
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_1354() {
62    }
63}
64