Given an array containing N numbers, we need to split the array into two subsets, such that each subset contains N/2 numbers, and the difference between the sum of the two subsets is minimised. I was able to come up with this :
A[i][j][k] = 1 if there is a subset of size ‘k’ of the first ‘i’ elements that has sum ‘j’. Fill this, and then check A[N][j][N/2] for all j and pick whichever minimises the difference. I want to know if there is a faster way of doing this.