CodeChef Mahesh and his lost array

題目鏈接:http://www.codechef.com/problems/ANUMLA

題意

給定n個數字集合的每個子集對應的數字的和
求n個數字分別是多少,按非降序輸出

解法

設arr表示n個數字的集合,sum表示子集的和的集合
首先對sum排序,將第一個0排除
枚舉sum,數組中第一個最小的數字肯定是n個數字中的一個
count表示前i個數字的和對應出現的次數
如果count中包含sum[i]那麼sum[i]肯定不在arr中
如果不包含sum[i]那麼枚舉arr的非空子集的和然後加上sum[i]將其放到count中去
重複即可

class ANUMLA {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n=in.nextInt();
        int[] a=new int[1<<n];
        for(int i=0;i<a.length;i++) a[i]=in.nextInt();
        Arrays.sort(a);
        HashMap<Integer,Integer> count=new HashMap<Integer, Integer>();
        ArrayList<Integer> arr=new ArrayList<Integer>();
        for(int u:a) {
            if(u==0) continue;
            if(!count.containsKey(u)) {
                for(int i=1;i<(1<<arr.size());i++) {
                    int sum=u;
                    for(int j=0;j<arr.size();j++) {
                        if((i&(1<<j))>0) sum+=arr.get(j);
                    }
                    int ti=count.containsKey(sum)? count.get(sum):0;
                    count.put(sum,ti+1);
                }
                arr.add(u);
            }else if(count.get(u)>1) {
                count.put(u,count.get(u)-1);
            }else {
                count.remove(u);
            }
        }
        for(int u:arr) {
            out.print(u+" ");
        }
        out.println();
    }
}