Which Algorithm need to implement to avoid the tle and wa

[singhnavneet]

Problem Statement
As Google headquarters have more and more workers, they decided to divide the departments in the headquarters into two groups and stagger their lunch breaks.

Google headquarters have N departments, and the number of people in the i-th department (1≤i≤N)(1≤i≤N) is Ki.

When assigning each department to Group A or Group B, having each group take lunch breaks at the same time, and ensuring that the lunch break times of Group A and Group B do not overlap, find the minimum possible value of the maximum number of people taking a lunch break at the same time.
In other words, find the minimum possible value of the larger of the following: the total number of people in departments assigned to Group A. and the total number of people in departments assigned to Group B.

Constraints​

• 2≤N≤20
• 1≤Ki≤10^8
• All input values are integers.
  
  
  

• Input​

  The input is given from Standard Input in the following format:
  N
  K1 K2 …… KN
  
  

  Output​

  Print the minimum possible value of the maximum number of people taking a lunch break at the same time.
  
  Test Case
• 6
  22 25 26 45 22 31
  
  Output
  89