차수열 (Degree Sequence)

# Havel-Hakimi algorithm
from heapq import nlargest
​
def is_graphic(d):
  d = sorted(d, reverse=True)
  while d and d[-1] == 0:
      d.pop()
  if not d:
      return True
  x = d[0]
  d = d[1:]
  if x > len(d):
      return False
  for i in range(x):
      d[i] -= 1
      if d[i] < 0:
          return False
  return is_graphic(d)
​
n = int(input())
d = list(map(int, input().split()))
print(1 if is_graphic(d) else -1)

// Havel-Hakimi in Java
import java.util.*;
public class Main {
  static boolean hh(ArrayList<Integer> d) {
      while (true) {
          Collections.sort(d, Collections.reverseOrder());
          while (!d.isEmpty() && d.get(d.size()-1) == 0)
              d.remove(d.size()-1);
          if (d.isEmpty()) return true;
          int x = d.remove(0);
          if (x > d.size()) return false;
          for (int i = 0; i < x; i++) {
              d.set(i, d.get(i) - 1);
              if (d.get(i) < 0) return false;
          }
      }
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      ArrayList<Integer> d = new ArrayList<>();
      for (int i = 0; i < n; i++) d.add(sc.nextInt());
      System.out.println(hh(d) ? 1 : -1);
  }
}