fork download
  1. import java.util.*;
  2. public class Main {
  3. public static void main(String[] args) {
  4. Scanner scanner = new Scanner(System.in);
  5. int n = scanner.nextInt();
  6. int[] chocolates = new int[n];
  7. int totalSum = 0;
  8.  
  9. for (int i = 0; i < n; i++) {
  10. chocolates[i] = scanner.nextInt();
  11. totalSum += chocolates[i];
  12. }
  13. scanner.close();
  14. // If total chocolates is odd, cannot divide equally
  15. if (totalSum % 2 != 0) {
  16. System.out.println("NO");
  17. return;
  18. }
  19. int target = totalSum / 2;
  20. // DP approach to check if there exists a subset with sum = target
  21. if (canPartition(chocolates, target)) {
  22. System.out.println("YES");
  23. } else {
  24. System.out.println("NO");
  25. }
  26. }
  27. // Function to check if we can partition into two equal subsets
  28. private static boolean canPartition(int[] chocolates, int target) {
  29. int n = chocolates.length;
  30. boolean[] dp = new boolean[target + 1];
  31. dp[0] = true; // Base case: sum 0 is always possible
  32. for (int num : chocolates) {
  33. for (int j = target; j >= num; j--) {
  34. dp[j] |= dp[j - num]; // If dp[j - num] was true, then dp[j] can be true
  35. }
  36. }
  37. return dp[target];
  38. }
  39. }
  40.  
Success #stdin #stdout 0.17s 54628KB
stdin
4  
1 2 3 4
stdout
YES