Problem: Given is a set of n integers, a$1,$ a$2,...,$ an$,,$ split the set into two subsets A and B$,$ if

possible, such that $|$n

i$=1$ai in A $|=|$n

i$=1$bi in B $|$ and A $\backslash$cap B $=\backslash$phi $.$

You are required to:

$1.$ Implement a brute force Backtracking algorithm to find that.

$2.$ Implement an algorithm that uses Backtracking with Heuristics to implement the above

problem.

$3.$ Provide the time difference in finding the solution for the problem with the above approaches.

Implement your algorithm in C$++$ or Java. Here is specification for the input an output of your

program.

Input: Standard input. First line provides total number of elements in the set. Then the next n

lines give the elements of that set.

Sample input:

$5$

$1$

$2$

$3$

$4$

$5$

Output:

$5+1=4+2$

$5+2=4+3$

$($etc$)$