篮球队编程题(Java)

题目

小Q是篮球训练队的教练，篮球队新加入了N名队员，第i名队员的篮球水平值为ai。
小Q现在要把他们按照以下的要求分为A队和B队进行训练:
1、A队的队员水平值之和严格大于B队的队员水平值之和
2、对于A队中的任意一名队员，如果把他分配到B队，A队的水平值之和就会严格小于B队的水平值之和。
3、每个队员必须要加入一个队伍
小Q现在想知道有多少种方案可以按照以上要求完成分队。

输入描述:
输入包括两行, 输入的第一行为一个正整数n(2 <= N <= 50), 表示队员的数量。
第二行包括N个正整数 ai(1 <= ai <= 6 x 104), 表示每名队员的篮球水平值, 以空格分割。

输出描述:
输出一个正整数, 表示方案数。
示例1
输入
4
5 4 7 6
输出
2

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringJoiner;
public class Main {
  private static List<Integer> stack = new ArrayList<Integer>();
    private static int[] savenumber = null;
    private static List<String> result = new ArrayList<String>();

    public static void main(String[] args) {
        String res;
        Integer each=0,a=0,b,sum=0;
        Integer min=1000;
        Scanner scanner = new Scanner(System.in);
        int k=scanner.nextInt();
        savenumber = new int[k];
        for(int i=0;i<k;i++){
               savenumber[i] = scanner.nextInt();
                 sum+=savenumber[i];
        }
            //循环找出 子集长度为 1,2,3...的子集
            for (int i = 1; i <= k; i++) {
                findAllSubSet(i, 1, 0);
            }
       
        
           for(int j=0;j<result.size();j++)
           {    min=1000;
                 a=0;
               res=result.get(j);
               String temp[]=res.split(";");
               for(int d=0;d<temp.length;d++)
               { Integer t=Integer.parseInt(temp[d]);
                  if(t<min)
                   min=t;
                //   System.out.println(Integer.parseInt(temp[d]));
                 //  System.out.println("min="+min);
                   a+=t;
               }
            b=sum-a;
          //  System.out.println("a="+a);
           //        System.out.println("b="+b);
            if(a>b&&a<b+2*min)
                each++;
           }
        System.out.println(each);
        
    }
   private static void findAllSubSet(int index, int stackLength, int start) {
        for (int i = start; i < savenumber.length; i++) {
            //放入栈顶
            stack.add(i);
            //栈中数目和此次递归次数相同
            if (stackLength == index) {
                //组装子集
                StringJoiner stringJoiner = new StringJoiner(";");
                for (int j = 0; j < stack.size(); j++) {
                    stringJoiner.add(savenumber[stack.get(j)] + "");
                }
                //放入子集
                result.add(stringJoiner.toString());
            }
            //递归放入数据
            else
                findAllSubSet(index, stackLength + 1, i + 1);
            //取出栈顶元素
            stack.remove(stack.size() - 1);
        }
    }


}

我的思路就是找出这个数组的所有组合情况，即数组的所有子集，然后把子集的数的和赋值给a，表示a队的得分，数组的总和减去a队的得分就是b队的得分，然后比较a和b，if(a>b&&a<b+2*min)这个就是判定条件，a>b判断的是a是否严格大于b，a<b+2*min判断a队的任何一个人去b队后，a的得分是否严格小于b队。其中min是a队里面得分最少的队员。
假设a队任何一个队员去b队，该队员的得分为x，则有a-x<b+x，得到a<2*x，所以这里x取最小值可以求出临界条件。
代码写了挺久的吧，但是尴尬的是，时间复杂度太高了。

所以仅作为记录，后面自己再想办法优化。