Precompiled header files

There are .pch files are i always wonder what is that. Today i found nice article explains it on wikipedia.

Also the article little bit explains about forward declaration, which prevents from recompiling.

Subset sum problems

One of the classic DP problem stated as “Given a set of n numbers ai sum up to M, and any K ≤ M, whether there is a subset of the numbers such that they sum up to (hit) K? We assume n might be as big as 1000, but M or K is not too big.

Solution is easy, as follows:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(int argc, char** argv){
	int a[]={2,6,15,21,34};  //simple test array
	int n=sizeof(a)/sizeof(int);

	int m=0;
	for_each(a,a+n,[&m](int x){ m+=x;});

	int* M=new int[m+1];
	for(int i=0;i<=m;i++){
		M[i]=0;
	}
	M[0]=1;

	for(int i=0;i<n;i++){
		for(int j=m;j>=a[i];j--){
			M[j]|=M[j-a[i]];
		}
	}
	int k=55; //simple test num

	cout<<"Sum to "<<k<<" is "<<(M[k]?" possible":" not possible")<<endl;
}

Difference between # and ## in macros

#define x(i) x##i

When x(1) is invoked it becomes x1, since ## appends, while # gives arguments.