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;
}