#1354

Construct Target Array With Multiple Sums

master · 1795 · lc hard +32 · verified · 36.8% accepted · 2,114 likes · top 15%

Description

Starting from an array arr of n ones, you may repeatedly set arr[i] to the current total sum of arr for any index i. Determine whether it is possible to reach the given target array through any sequence of such operations. Return true if achievable, false otherwise.

Example 1:

Input: target = [9,3,5]

Output: true

Explanation: Start with arr = [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

Code

1

2

3

class Solution:
    def isPossible(self, target: List[int]) -> bool:

class Solution:
    def isPossible(self, target: List[int]) -> bool: