Medium Recursion > Backtracking with Pruning/Branch and Bound

You will be given an array of **N** elements. You have to partition two non-overlapping and non-empty subsequences such that the product of elements of first sub-sequences is **A**, and product of elements of second sub-sequences is **B**. Following conditions should meet, - A and B should be perfect square. - Position of last element of first sub-sequence should be less than position of first element of second sub-sequence, which is here Non-overlapping means. You have to **maximize** absolute difference between A and B. If it is not possible, print **-1**. Note: To know more about subsequence, see here: https://en.wikipedia.org/wiki/Subsequence Input: ------ First line of input will consist of an integer **T (T<=250)**, indicates the number of test cases follow. Each case starts with a line containing an integer **N, (1<=N<=15)**, indicates the length of array Arr. Next line contains **N** integers such that **1<=Arr[i]<=15**. Output: ------- For each test case you have to print the required answer. Sample Input ------------ 5 5 2 2 3 5 5 4 2 5 5 2 5 1 5 5 5 1 4 2 2 2 2 4 2 3 2 4 Sample Output ------------- 21 -1 24 0 0

Bir Bahadur Khatri