CareerCup

This is a variation of well-known NP-problem (en.wikipedia.org/wiki/Partition_problem). So the only solution is backtracking.

I allowed myself to write the implementation using DP approach:

public static void main(String[] args) {

		// int[] arr = { 5, 7, 3, 3 };
		int[] arr = { 3, 2, 1 };
		// int[] arr = { 1, 5, 11, 5 };
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
		}
		System.out.println("Sum: " + sum);
		boolean[][] sums = new boolean[arr.length][sum + 1];
		for (int i = 0; i < sums.length; i++) {
			sums[i][0] = true;
		}
		sums[0][arr[0]] = true;
		for (int i = 1; i < sums.length; i++) {
			for (int j = 0; j < sums[0].length; j++) {
				if (sums[i - 1][j] == true) {
					sums[i][j] = true;
					sums[i][j + arr[i]] = true;
				}
			}
		}
		// printMatrix(sums);
		int half = sum / 2;
		while (!sums[sums.length - 1][half]) {
			half--;
		}
		System.out.println("Closest to half of the sum: " + half);
		Set<Integer> firstHalfIndexes = new HashSet<Integer>();
		int rowWithHalf = sums.length - 1;
		while (half > 0) {
			while (rowWithHalf >= 0 && sums[rowWithHalf][half]) {
				rowWithHalf--;
			}
			rowWithHalf++;
			firstHalfIndexes.add(rowWithHalf);
			half -= arr[rowWithHalf];
		}
		List<Integer> firstHalf = new ArrayList<Integer>(firstHalfIndexes.size());
		List<Integer> secHalf = new ArrayList<Integer>(arr.length - firstHalfIndexes.size());
		for (int i = 0; i < arr.length; i++) {
			if (firstHalfIndexes.contains(i)) {
				firstHalf.add(arr[i]);
			} else {
				secHalf.add(arr[i]);
			}
		}
		System.out.println("First team: " + firstHalf);
		System.out.println("Sec team: " + secHalf);
		System.out.println("Diff: " + Math.abs(firstHalf.size() - secHalf.size()));
	}

{
General Approach:-
Sort the elements into descending order.
Divide the array into 1 and n-1 sub arrays
Find the sum difference if it is equal you got the solution otherwise move the smallest element from set 2 to set one and keep on checking until you got the sum equal.

}

Here is some code about the problem.

int splitPlayers(int[] set) {

int n = set.length;
int sum = 0;

for(int s:set) {
sum += s;
}
sum /= 2;
boolean[][] subset = new boolean[sum+1][n];
int[][] count = new int[sum+1][n];

subset[set[0]][0] = true;
count[set[0]][0] = 1;

for (int i = 1; i <= sum; i++) {
for (int j = 0; j < n; j++) {
if (set[j] == i) {
subset[i][j] = true;
count[i][j] = 1;
} else if (j > 0) {
if (i >= set[j]) {
subset[i][j] = subset[i][j-1] || subset[i - set[j]][j-1];
if (subset[i - set[j]][j-1] == true) {
count[i][j]=count[i - set[j]][j-1]+1;

} else if(subset[i][j-1]==true) {
count[i][j] = count[i][j-1];
}
}
else {
subset[i][j] = subset[i][j-1];
}
}
}
}
if(!subset[sum][n-1]){
return 0;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (count[sum][i] != 0) {
int onepart = n - count[sum][i];
int other = n - onepart;
min = Math.min(min, Math.abs(onepart-other));
}

}
return min;





}

I implemented in dp but i couldnt find bug in my code can anybody help.Logic for every value from last i check whether to put in which optimal team.
#include<stdio.h>
int findMin(int a,int b){
if(a<b)
return a;
else
return b;
}

int findDifference(int arr[3],int n,int firstsum,int secondsum,int firstcount,int secondcount){

if(n<0){
if(firstsum == secondsum){
printf("%d\n",firstsum );
return firstcount -secondcount;
}
}
else
findMin(findDifference(arr,n-1,firstsum+arr[n],secondsum,firstcount++,secondcount),
findDifference(arr,n-1,firstsum,arr[n]+secondsum,firstcount,secondcount++));
}

int main()
{
int arr[]={3,1,6,3,1};
int size=3;
printf("%d\n",findDifference(arr,3,0,0,0,0) );

}

#include<stdio.h>
int findMin(int a,int b){
if(a<b)
return a;
else
return b;
}

int findDifference(int arr[3],int n,int firstsum,int secondsum,int firstcount,int secondcount){

if(n<0){
if(firstsum == secondsum){
printf("%d\n",firstsum );
return firstcount -secondcount;
}
}
else
findMin(findDifference(arr,n-1,firstsum+arr[n],secondsum,firstcount++,secondcount),
findDifference(arr,n-1,firstsum,arr[n]+secondsum,firstcount,secondcount++));
}

int main()
{
int arr[]={3,1,6,3,1};
int size=3;
printf("%d\n",findDifference(arr,3,0,0,0,0) );

}