import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class kie { public kie(List<Integer> notes) { int max_sum = 0; List<List<Integer>> subsets = this.subsets(notes); Iterator<List<Integer>> it = subsets.iterator(); while(it.hasNext()) { List<Integer> subset = it.next(); int subset_sum = partition_sum(subset); if (subset_sum > max_sum) { max_sum = subset_sum; } } if (max_sum > 0) { System.out.println(max_sum); } else { System.out.println("NIESTETY"); } } private int set_sum(List<Integer> numbers) { int sum = 0; Iterator<Integer> it = numbers.iterator(); while(it.hasNext()) { sum += it.next(); } return sum; } private int partition_sum(List<Integer> subset) { int set_sum = this.set_sum(subset); if (set_sum % 2 != 0) { return 0; } int limit = set_sum / 2; if (sub_sum(subset, limit)) { return set_sum; } return 0; } private boolean sub_sum(List<Integer> subset, int limit) { for (List<Integer> sub : subsets(subset)) { if(set_sum(sub) == limit) { return true; } } return false; } private List<Integer> createInnerSet(Integer i) { List<Integer> result = new LinkedList<Integer>(); result.add(i); return result; } private List<List<Integer>> subsets(List<Integer> inset) { List<List<Integer>> result; if (inset.size() <= 1) { result = new LinkedList<List<Integer>>(); result.add(new LinkedList<Integer>(inset)); return result; } int pivot = inset.get(0); result = subsets(inset.subList(1, inset.size())); List<List<Integer>> new_sets = new LinkedList<List<Integer>>(); new_sets.add(createInnerSet(pivot)); Iterator<List<Integer>> it = result.iterator(); while (it.hasNext()) { List<Integer> old_set = it.next(); List<Integer> new_set = new LinkedList<Integer>(old_set); new_set.add(pivot); new_sets.add(new_set); } result.addAll(new_sets); return result; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); List<Integer> notes = new ArrayList<Integer>(n); for (int i = 0; i < n; i++) { notes.add(in.nextInt()); } new kie(notes); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class kie { public kie(List<Integer> notes) { int max_sum = 0; List<List<Integer>> subsets = this.subsets(notes); Iterator<List<Integer>> it = subsets.iterator(); while(it.hasNext()) { List<Integer> subset = it.next(); int subset_sum = partition_sum(subset); if (subset_sum > max_sum) { max_sum = subset_sum; } } if (max_sum > 0) { System.out.println(max_sum); } else { System.out.println("NIESTETY"); } } private int set_sum(List<Integer> numbers) { int sum = 0; Iterator<Integer> it = numbers.iterator(); while(it.hasNext()) { sum += it.next(); } return sum; } private int partition_sum(List<Integer> subset) { int set_sum = this.set_sum(subset); if (set_sum % 2 != 0) { return 0; } int limit = set_sum / 2; if (sub_sum(subset, limit)) { return set_sum; } return 0; } private boolean sub_sum(List<Integer> subset, int limit) { for (List<Integer> sub : subsets(subset)) { if(set_sum(sub) == limit) { return true; } } return false; } private List<Integer> createInnerSet(Integer i) { List<Integer> result = new LinkedList<Integer>(); result.add(i); return result; } private List<List<Integer>> subsets(List<Integer> inset) { List<List<Integer>> result; if (inset.size() <= 1) { result = new LinkedList<List<Integer>>(); result.add(new LinkedList<Integer>(inset)); return result; } int pivot = inset.get(0); result = subsets(inset.subList(1, inset.size())); List<List<Integer>> new_sets = new LinkedList<List<Integer>>(); new_sets.add(createInnerSet(pivot)); Iterator<List<Integer>> it = result.iterator(); while (it.hasNext()) { List<Integer> old_set = it.next(); List<Integer> new_set = new LinkedList<Integer>(old_set); new_set.add(pivot); new_sets.add(new_set); } result.addAll(new_sets); return result; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); List<Integer> notes = new ArrayList<Integer>(n); for (int i = 0; i < n; i++) { notes.add(in.nextInt()); } new kie(notes); } } |