Balance The Array

ArrayDynamic Programming

Given an array of integers, determine if it is possible to split the array into two non-empty parts such that the sum of elements in both parts is the same. Return YES if it can be split this way, otherwise return NO.

Example 1

Input

[
  1,
  5,
  3,
  1,
  1,
  1,
  5
]

Output

YES

Explanation. We can split the array after the third element: [1, 5, 3] and [1, 1, 1, 5]. Both parts sum to 9.

Example 2

Input

[
  10,
  20
]

Output

Explanation. It is not possible to split the array such that both parts have an equal sum.

Example 3

Input

[
  1,
  2,
  3,
  4,
  10
]

Output

YES

Explanation. Splitting after the fourth element results in two parts, [1, 2, 3, 4] and [10], which both sum to 10.

Example 4

Input

[
  2,
  1,
  2,
  1,
  2,
  3
]

Output

Explanation. There is no possible way to split the array into two parts where the sums are equal.

Follow-up: Can you solve this problem in O(n) time complexity and O(1) extra space?

Constraints:

- You may not sort or modify the original array.\n- The array will contain at least 2 elements.

Views: 3