Rajesh kumar jena//Prroblem4

public class Problem4 {
public int minDiff;

// a utility method that tries each and every solution
// possible by invoking itself recursively
void recursive(int array[], int size, boolean currElements[], int noOfSelectedElements, boolean sol[], int sum,
		int currSum, int currPosition) {
	// checking whether the currPosition
	// is going out of the bound or not
	if (currPosition == size) {
		return;
	}

	// checking for the numbers of remaining elements  
	// are not less than the number of elements required  
	// to construct the solution  
	if ((size / 2 - noOfSelectedElements) > (size - currPosition)) {
		return;
	}

	// consider the cases when current element  
	// is not included in the solution  
	recursive(array, size, currElements, noOfSelectedElements, sol, sum, currSum, currPosition + 1);

	// adding the current element   
	// to the solution  
	noOfSelectedElements = noOfSelectedElements + 1;
	currSum = currSum + array[currPosition];
	currElements[currPosition] = true;

	// checking whether the solution is formed or not  
	if (noOfSelectedElements == size / 2) {
		// checking whether the solution build is  
		// better than the best solution found so far  
		if (Math.abs(sum / 2 - currSum) < minDiff) {
			minDiff = Math.abs(sum / 2 - currSum);
			for (int j = 0; j < size; j++) {
				sol[j] = currElements[j];
			}
		}
	} else {
		// the following recursive call includes the current element  
		// in the solution  
		recursive(array, size, currElements, noOfSelectedElements, sol, sum, currSum, currPosition + 1);
	}

// removing the current element
// before returning to the caller
// of this method
currElements[currPosition] = false;
}

// main method that generates an array
void display(int array[]) {
int size = array.length;

// the boolean array that contains the
// inclusion and exclusion of an element
// in current set. The number excluded
// automatically form the other set
boolean[] currElements = new boolean[size];

// The inclusion/exclusion array for
// final solution
boolean[] sol = new boolean[size];

	minDiff = Integer.MAX_VALUE;

	int sum = 0;
	for (int j = 0; j < size; j++) {
		sum = sum + array[j];
		currElements[j] = sol[j] = false;
	}

// Find the solution using recursive
// function TOWUtil()
recursive(array, size, currElements, 0, sol, sum, 0, 0);

// Displaying the solution
System.out.print("The elements of the first subset are: ");
for (int j = 0; j < size; j++) {
if (sol[j] == true) {
System.out.print(array[j] + " ");
}
}

	System.out.print("\n");
	System.out.print("The elements of the second subset are: ");
	for (int j = 0; j < size; j++) {
		if (sol[j] == false) {
			System.out.print(array[j] + " ");
		}
	}
}

// Main method
public static void main(String[] argvs) {
// the input array
int array[] = new int[] {3,4,5,3,100,1,83,54,23,20};

	// computing the size of the input array  
	int size = array.length;

	// creating an object of the class TugOfWarEx             
	Problem4 obj = new Problem4();

	System.out.println("For the array: ");
	for (int i = 0; i < size; i++) {
		System.out.print(array[i] + " ");
	}

	System.out.println();

	// invoking the method tugOfWar()   
	obj.display(array);

	// updating input array  
	

	array = new int[] { 1, 3, 3, 4, 5, 20, 23, 54, 83, 100 };

	// computing the size of the input array  
	size = array.length;

	System.out.println("\n");

	System.out.println("For the array: ");
	for (int i = 0; i < size; i++) {
		System.out.print(array[i] + " ");
	}

	System.out.println();

	// invoking the method tugOfWar()   
	obj.display(array);
	//Program @Rajesh

}

}