/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] a =  {-3, 5, -12,14,-9,13};
		int[] b =  {-3,14, 12, 5,-9,13};
		System.out.println(canPartitioning(a));
		System.out.println(canPartitioning(b));
	}
 
	static boolean canPartitioning(int[] arr) {
	    return partition(arr, 0, 0, 0, 0);
	}
 
	 static boolean partition(int[] arr, int i, int selected, int sum, int rest) {
         int length = arr.length;
		 if (i >= length)  return selected == length/2 && sum == rest;
         return selected <length/2 && partition(arr, i + 1, selected + 1, sum + arr[i], rest)
             || partition(arr, i + 1, selected, sum, rest + arr[i]);
     }
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB0aHJvd3MgamF2YS5sYW5nLkV4Y2VwdGlvbgoJewoJCWludFtdIGEgPSAgey0zLCA1LCAtMTIsMTQsLTksMTN9OwoJCWludFtdIGIgPSAgey0zLDE0LCAxMiwgNSwtOSwxM307CgkJU3lzdGVtLm91dC5wcmludGxuKGNhblBhcnRpdGlvbmluZyhhKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKGNhblBhcnRpdGlvbmluZyhiKSk7Cgl9CgkKCXN0YXRpYyBib29sZWFuIGNhblBhcnRpdGlvbmluZyhpbnRbXSBhcnIpIHsKCSAgICByZXR1cm4gcGFydGl0aW9uKGFyciwgMCwgMCwgMCwgMCk7Cgl9CgoJIHN0YXRpYyBib29sZWFuIHBhcnRpdGlvbihpbnRbXSBhcnIsIGludCBpLCBpbnQgc2VsZWN0ZWQsIGludCBzdW0sIGludCByZXN0KSB7CiAgICAgICAgIGludCBsZW5ndGggPSBhcnIubGVuZ3RoOwoJCSBpZiAoaSA+PSBsZW5ndGgpICByZXR1cm4gc2VsZWN0ZWQgPT0gbGVuZ3RoLzIgJiYgc3VtID09IHJlc3Q7CiAgICAgICAgIHJldHVybiBzZWxlY3RlZCA8bGVuZ3RoLzIgJiYgcGFydGl0aW9uKGFyciwgaSArIDEsIHNlbGVjdGVkICsgMSwgc3VtICsgYXJyW2ldLCByZXN0KQogICAgICAgICAgICAgfHwgcGFydGl0aW9uKGFyciwgaSArIDEsIHNlbGVjdGVkLCBzdW0sIHJlc3QgKyBhcnJbaV0pOwogICAgIH0KfQ==