PKU 3628 Bookshelf 2

http://poj.org/problem?id=3628
n(<=20)匹の牛がいて、それぞれ高さh_iである。
何匹か積み上げて高さs>=bにしたい。
この時、s-bの最小値を求めよというような問題。
TLEなりにくいようです。

全探索っぽく書いて普通に通りました。

int in[20];
int insum[21];
int n,b;
ll ans=100000000LL;

void dfs(int ne,ll sum){
  if(sum+insum[n]-insum[ne]<b)return;
  if(sum>=b){
    ans=min(ans,sum-b);
    return;
  }
  for(int i=ne;i<n;i++)
    dfs(i+1,sum+in[i]);
}


main(){
  cin>>n>>b;
  rep(i,n){
    cin>>in[i];
    insum[i+1]=insum[i]+in[i];
  }
  dfs(0,0);
  cout<<ans<<endl;
}

(追記)何を勘違いしたのO(N!)だと考えていたようです。