i need Given a set of numbers on the command line (partition an array)
It should check whether a solution exists and if so  print the two sets

upto now the code i have seems to parttion each integer, what i need is for it to partition the array as a whole, for example lets take the array[1,2,3] this can be divided as [1,2] and [3], we can see that these two subsets have an equal sum.

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication2;

import java.util.ArrayList;
import java.util.Collection;

public class Partition {
    private static int arrayNumber = 0;
    private static Collection<Integer> s1 = new ArrayList<Integer>();
    private static Collection<Integer> s2 = new ArrayList<Integer>();

    public static void partition(int n) {
        partition(n, n, "");
    }
    
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            arrayNumber++;
            String[] s = prefix.split(" ");
            if (arrayNumber == 2) {
                addtoArray(s, s1);
            } else if(arrayNumber == 3) {
                addtoArray(s, s2);
            }
            //System.out.println("--------------");
            //System.out.println(prefix);

            return;
        }

        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }

    private static void addtoArray(String s[], Collection<Integer> col) {
        for (int i = 0; i < s.length; i++) {
            String numStr = s[i];
            if (numStr.equals("")) {
                continue;
            }
            int num = Integer.parseInt(numStr);
            col.add(num);
        }
    }


    public static void main(String[] args1) {
        String[] args = {"6", "2", "4"};

        for (int i = 0; i < args.length; i++) {
            arrayNumber = 0;
            String str = args[i];
            int n = Integer.parseInt(str);
            partition(n);
        }

        for (int number : s1) {
            System.out.print(number + " ");
        }

        System.out.println("");
        for (int number : s2) {
            System.out.print(number + " ");
        }
        System.out.println("");
    }

}

PLEASE HELP

check whether a solution exists

Could you define what a solution is? How are the numbers to be partitioned?

Sounds like you need an algorithm for solving the problem? What do you have so far?

Partition Problem
“The problem is to decide whether a given multiset of  integers can be partitioned into two "halves" that have  the same sum. More precisely, given a multiset S of  integers, is there a way to partition S into two subsets S1  and S2 such that the sums of the numbers in each  subset are equal? The subsets S1 and S2 must form a  partition in the sense that they are disjoint and they  cover S.”

what i need fr my code to do is
solve the partition problem
Given a set of numbers on the command line
It should check whether a solution exists and if so  print the two sets

Ok. Got it. For example given {10, 6, 4} the results would be: {10} and {4,6}
What is your design so far?

exactly.

i sent u my code above. but that doesnt work. it seems to divide off numbers, say array[2,4,6], it comes as 1,1 2,2 3,3, doesnt divide the array only the integers one by one

Before you code a program you need to design it. Writing code before getting a design wastes a lot of time.
Do you have a design for how you are going to read and partition a set of numbers?

Do you have a design or algorithm on how to solve this problem? Given that, we can help you write a java program to do it.

Have you tried Google for an algorithm that shows the logic needed to solve this?

Yes finding the proper algorithm is the key to solve this problem,
I just tried with a straight forward algorithm(i.e to checck all possible sums in a proper sequence).

This may not be the best but works fine.

Sorry for not using comments.

Here is the code.
I also placed the sample output here.

Cool.

/*
 * 
 * author thamilvaanan
 * 
 * 
 */



import java.util.ArrayList;
import java.util.Collection;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Collections;

public class Partition {
	
 //private ArrayList<Integer> inputArray = new ArrayList<Integer>(); 
	
	
 public Partition(){
	 
 
 findPair(getInput());
	
	 
 }

 
 
	private void findPair(List<Integer>  arrayInput) {
		 List<Integer> dynamicArrayPosition= new ArrayList<Integer>();
		 int totalSum=0;	 
		 totalSum=findTotalSum(arrayInput);
	     int currentSum=0; 
	     int length=arrayInput.size()/2;
	     int inputArrayLength=arrayInput.size();
	     boolean isSubsetsFound=false;
		 for(int i=1; i<=length; i++)
		 {
			 dynamicArrayPosition= getDynamicArrayPosition(i);
			 
			 
			 for(int j=1; j<=getcombinations(arrayInput.size(),i); j++)
			 {
				 currentSum=0;
	             int k=0;
				 while ( k<i && dynamicArrayPosition.get(k)< inputArrayLength)
				 {
					//System.out.println("i"+i+", k"+k+"dynamicArrayPosition.get(k)"+dynamicArrayPosition.get(k)); 
					 //System.out.println("sdfsdf"+arrayInput.get(dynamicArrayPosition.get(k)));
					currentSum +=  arrayInput.get(dynamicArrayPosition.get(k)) ;
					//System.out.println("currentSumIn"+currentSum);
				    k++;
				 }
				 //System.out.println("currentSum"+currentSum);
				 if(currentSum==totalSum-currentSum)
				 {
					isSubsetsFound=true; 
					
					outputAnswer(dynamicArrayPosition,arrayInput);
					
					break; 
				 }
				 
				//System.out.println("dynamicArrayPosition.get(k)"+dynamicArrayPosition.get(i-1)); 
				//System.out.println("inputArrayLength"+inputArrayLength); 		 
				 if( dynamicArrayPosition.get(i-1) >= inputArrayLength -1  )
				 {
					 //System.out.println("inputArrayLength");
					 dynamicArrayPosition = dynamicArrayPositionHandler(i,inputArrayLength, dynamicArrayPosition);
				 }
				 else
				 {
					 dynamicArrayPosition.set(i-1,dynamicArrayPosition.get(i-1)+1);
				 }
				 
			 }
	                  
		 	 if(isSubsetsFound)
		 	 {
		 		break; 
		 	 }
		 }
	 	 if(!isSubsetsFound)
	 	 {
			System.out.println("........................");
			System.out.println("Equal sum subsets not found");	
	 	 }
	}

	private void outputAnswer(List<Integer> dynamicArrayPosition, List<Integer>  arrayInput) {
		List<Integer> set1= new ArrayList<Integer>();
		List<Integer> set2= new ArrayList<Integer>();
		System.out.println("........................");
		System.out.println("Equal sum subsets found");	
		int length=dynamicArrayPosition.size();
		 for(int i=0; i<length; i++)
		 {
		 	set1.add(arrayInput.get(dynamicArrayPosition.get(i)));				 
		 }
		Iterator<Integer> iterator= arrayInput.iterator();
		while (iterator.hasNext())
		{
			if (set1.contains(iterator.next()))
				iterator.remove();
		}
		set2= arrayInput;
		System.out.println(set1+" = "+set2+" = "+findTotalSum(arrayInput));
			
		
	}

	public int factorial(int number)
	{
		int result=1;
		for(int i=number; i> 1; i--)
		{
			result*=i;
		}
		return result;
	}
	
	public int getcombinations(int var1,int var2 )
	{
		int result=1;		
		result= factorial(var1)/(factorial(var1-var2)*factorial(var2));
		return result;
	}
	
	public void totalPossibleTwoPairSets(List<Integer>  arrayIn)
	{
		List<Integer> arrayInput= arrayIn;
		int numberOfCombinations=0;
		 
		

		Collections.sort(arrayInput);
		
		 for(int i=1; i<=arrayInput.size()/2; i++){
		 	 
		 numberOfCombinations+= getcombinations(arrayInput.size(),i); 
				                  
		 
		 }
		System.out.println("Total Possible Two Pair Sets:"+numberOfCombinations); 
	}
	
	
	
	public int findTotalSum(List<Integer>  arrayIn)
	{
		int result=0;
		
		 for(int i=0; i<arrayIn.size(); i++)
		 {
			 result+= arrayIn.get(i);	                  			 
		 }
		
		return result;
	}
	
	public List<Integer> getDynamicArrayPosition(int index)
	{
		List<Integer> dynamicArrayPosition= new ArrayList<Integer>();
		 for(int i=0; i<index; i++)
		 {        
			 dynamicArrayPosition.add(i);
		 }
		return dynamicArrayPosition;
	}

	public List<Integer> dynamicArrayPositionHandler(int index,int length,List<Integer> lastPositions)
	{
		 
		 for(int i=index-1; i>=0; i--)
		 {  
			// System.out.println("lastPositions.get(i)"+lastPositions.get(i)); 
			//  System.out.println("length-(index-i)"+(length-(index-i))); 
			//  System.out.println(lastPositions.get(i)==((length-(index-i)))); 
		   if(lastPositions.get(i) == (length-(index-i)) && i>0 )
		   {
			 //  System.out.println("length-(index-i)"+(length-(index-i))); 
			   lastPositions.set(i-1, lastPositions.get(i-1)+1);
			   lastPositions.set(i, lastPositions.get(i-1)+1);
		   }   
			 
		 }
		// System.out.println("lastPositions"+lastPositions); 
		return lastPositions;
	}
 
 private List<Integer>  getInput() throws InputMismatchException {
  
	List<Integer> tempList = new ArrayList<Integer>(); 
    Scanner sc = new Scanner(System.in);
    
    int currentInt;
    
   
    System.out.println("Enter Numbers with a space");
	 
    
    String numberString= sc.nextLine();
    
	StringTokenizer st1 = new StringTokenizer(numberString);	
 
    while (st1.hasMoreTokens() )
	{   	 
     currentInt= Integer.parseInt(st1.nextToken());      
	 tempList.add(currentInt);	 	   
    }
 
    
	System.out.println("Your Input : "+tempList);
	return tempList;
}
 


 public static void main(String args[])
 {
 
    Partition partition= new Partition();
	 
	 
 }
 	

}

Enter Numbers with a space
5 3 9 6 1
Your Input : [5, 3, 9, 6, 1]
........................
Equal sum subsets found
[3, 9] = [5, 6, 1] = 12

This article has been dead for over six months. Start a new discussion instead.