未通过的1011——堆栈方式

import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.List;import java.util.Scanner;import java.util.Stack;public class Main {public static void main(String[] args) {new Main();}public Main() {Scanner s = new Scanner(System.in);while (s.hasNextInt()) {// 获得长度int count = s.nextInt();if (count == 0) {break;}int[] nums = new int[count];// 获得数组、和int sum = 0;for (int i = 0; i < count; i++) {int num = s.nextInt();sum += num;nums[i] = num;}// 排序Arrays.sort(nums);// 最大值int max = nums[count - 1];// 遍历可能的结果for (int i : getList(sum)) {if (max <= i) {if (exec(nums, i, sum)) {break;}}}}s.close();}public boolean exec(int[] nums, int l, int sum) {// 数组长度int size = nums.length;// 可变总长int s = l;// 堆栈Stack<Integer> stack = new Stack<Integer>();// 标记boolean[] flags = new boolean[size];// 初始化iint i = size - 1;while (true) {for (; i >= 0; i--) {// 如果剩余可用数之和不够，passif (!isEnough(nums, flags, i, s)) {break;}// 如果当前数不可用，passif (flags[i]) {continue;}int n = nums[i];// 如果大于和，passif (n > s) {continue;}// 如果跟上一个可用数一样，passif (i + 1 < size && n == nums[i + 1] && !flags[i + 1]) {continue;}// 标记已用flags[i] = true;// 进栈stack.push(i);// 从和中减掉s -= n;if (s == 0) {sum -= l;// 判断是否全部用尽if (sum == 0) {System.out.println(l);return true;} else {// 再次轮回匹配剩余的可用数i = size - 1;s = l;}}}// 可用数用尽，当前匹配也没成功// 恢复最后的数int top = stack.pop();flags[top] = false;s += nums[top];if (s == l) {sum += l;if (!stack.isEmpty()) {top = stack.pop();flags[top] = false;s = nums[top];}}// 如果是边缘，恢复倒数第二个数if (top == 0) {top = stack.pop();flags[top] = false;s += nums[top];}// 如果弹出的数是栈中最后一个，匹配失败if (top == size - 1) {return false;}// 从下一个可用数开始i = top - 1;}}// 判断剩余可用数之和是否够public boolean isEnough(int[] nums, boolean[] flags, int begin, int sum) {for (int i = begin; i >= 0; i--) {if (!flags[i]) {sum -= nums[i];if (sum <= 0) {return true;}}}return false;}// 获得可能的结果Listpublic List<Integer> getList(int n) {List<Integer> list = new ArrayList<Integer>();for (int i = 1; i <= Math.sqrt(n); i++) {if (n % i == 0) {list.add(i);if (i * i != n) {list.add(n / i);}}}Collections.sort(list);return list;}}