Read problems statements in Mandarin Chinese and Russian as well. 

Mahesh got a beautiful array named A as a birthday gift from his beautiful girlfriend Namratha. There are N positive integers in that array. Mahesh loved the array so much that he started to spend a lot of time on it everyday. One day, he wrote down all possible subsets of the array. Then for each subset, he calculated the sum of elements in that subset and wrote it down on a paper. Unfortunately, Mahesh lost the beautiful array :(. He still has the paper on which he wrote all subset sums. Your task is to rebuild beautiful array A and help the couple stay happy :)

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.
First line of each test case contains one integer N, the number of elements in A.
Second line of each test case contains 2^{N} integers, the values written on paper

------ Output ------ 

For each test case, output one line with N space separated integers in non-decreasing order.

------ Constraints ------ 

$1 ≤ T ≤ 50
$$1 ≤ N ≤ 15
$$0 ≤ Values on paper ≤ 10^{9}
$$All input values are valid. A solution always exists

------ Example ------ 

------ Input Format ------ 

2
1
0 10
2
0 1 1 2

------ Output Format ------ 

10
1 1

------ Explanation ------ 

Test case #2
For the array [1,1], possible subsets are {}, {1}, {1}, {1,1}, respective sums are 0, 1, 1, 2.

Source: codechef | Difficulty: HARD
Tags: Sorting

Data structures

Mathematics

Greedy algorithms


Solutions:
import heapq
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	arr.pop(0)
	ans = []
	pq = []
	subsets = []
	for val in arr:
		if pq and val == pq[0]:
			heapq.heappop(pq)
		else:
			ans.append(val)
			for i in range(len(subsets)):
				subsets.append(subsets[i] + val)
				heapq.heappush(pq, subsets[i] + val)
			subsets.append(val)
	print(*ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	x = 2 ** n
	a1 = []
	a2 = []
	l = {}
	y = list(map(int, input().split()))
	y.sort()
	for i in range(1, x):
		if y[i] in l and l[y[i]] != 0:
			l[y[i]] -= 1
		else:
			t = []
			for j in a1:
				t.append(j + y[i])
			for j in a2:
				t.append(j + y[i])
			for j in t:
				if j not in l:
					l[j] = 0
				l[j] += 1
				a1.append(j)
			a2.append(y[i])
			if len(a2) == n:
				break
	print(*a2)


def ans(arr, size):
	if size == 1:
		return [arr[1]]
	m = arr[1]
	new_arr = dict()
	now = list()
	for item in arr:
		if item - m in new_arr and new_arr[item - m] > 0:
			new_arr[item - m] -= 1
		else:
			if item in new_arr:
				new_arr[item] += 1
			else:
				new_arr[item] = 1
			now.append(item)
	prev = ans(now, size - 1)
	prev.append(m)
	return prev
cases = int(input())
for _ in range(cases):
	n = int(input())
	arr = list(map(int, input().split()))
	r = ans(sorted(arr), n)
	r.sort()
	print(' '.join(list(map(str, r))))


for _ in range(int(input())):
	n = int(input())
	n2 = 2 ** n
	sums = []
	ans = []
	rem = {}
	a = list(map(int, input().split()))
	a.sort()
	for i in range(1, n2):
		if a[i] in rem and rem[a[i]] != 0:
			rem[a[i]] -= 1
		else:
			temp = []
			for j in sums:
				temp.append(j + a[i])
			for j in ans:
				temp.append(j + a[i])
			for j in temp:
				if j not in rem:
					rem[j] = 0
				rem[j] += 1
				sums.append(j)
			ans.append(a[i])
			if len(ans) == n:
				break
	for i in ans[:-1]:
		print(i, end=' ')
	print(ans[-1])


import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sumset = []
	ans = []
	subs = []
	arr.sort()
	arr = arr[1:]
	for i in arr:
		if subs and i == subs[0]:
			heapq.heappop(subs)
		else:
			ans.append(i)
			tmp = []
			for j in sumset:
				tmp.append(j + i)
				heapq.heappush(subs, j + i)
			sumset.extend(tmp)
			sumset.append(i)
		if len(ans) == n:
			break
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(c) for c in input().split()]
	subset = []
	arr.sort()
	p = []
	ans = []
	x = 1
	while len(ans) != n:
		while len(p) > 0 and p[0] < arr[x]:
			p.pop(0)
		if p and p[0] == arr[x]:
			p.pop(0)
		else:
			ans.append(arr[x])
			subset.append(arr[x])
			for i in range(len(subset) - 1):
				subset.append(subset[i] + arr[x])
				p.append(subset[i] + arr[x])
		p.sort()
		x += 1
	print(*ans)


import heapq
import math
for _ in range(int(input())):
	required_array_length = int(input())
	array = []
	subsets_sums = [int(num) for num in input().split()]
	subsets_sums.sort()
	sums_queue = []
	previous_combinations_sums = []
	skip_num = subsets_sums.count(0)
	array.extend([0] * int(math.log2(skip_num)))
	current_sum = 0
	idx = skip_num
	while len(array) < required_array_length:
		candidate = subsets_sums[idx]
		idx += 1 * skip_num
		if current_sum == 0 and len(sums_queue) > 0:
			current_sum = heapq.heappop(sums_queue)
		if candidate == current_sum:
			current_sum = 0
			continue
		array.append(candidate)
		for i in range(len(previous_combinations_sums)):
			new_sum = previous_combinations_sums[i] + candidate
			heapq.heappush(sums_queue, new_sum)
			previous_combinations_sums.append(new_sum)
		previous_combinations_sums.append(candidate)
		if current_sum != 0:
			heapq.heappush(sums_queue, current_sum)
			current_sum = 0
	print(*array)


def anumla(sumset, n):
	valueset = []
	sum_arr = []
	rem = {}
	for i in range(2 ** n - 1):
		if sumset[i] in rem and rem[sumset[i]] != 0:
			rem[sumset[i]] -= 1
		else:
			sumsubset = []
			for el in valueset:
				sumsubset.append(el + sumset[i])
			for el in sum_arr:
				sumsubset.append(el + sumset[i])
			for el in sumsubset:
				if el not in rem:
					rem[el] = 0
				rem[el] += 1
				sum_arr.append(el)
			valueset.append(sumset[i])
			if len(valueset) == n:
				break
	return valueset
t = int(input())
for _ in range(t):
	n = int(input())
	sumset = list(map(int, input().split()))
	sumset.sort()
	print(*anumla(sumset[1:], n))


from math import ceil, sqrt, log, gcd
from collections import deque, defaultdict as dd
from os import path
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
t = int(input())
for f in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a.pop(0)
	t0 = []
	s = []
	while a:
		c = a.pop(0)
		t1 = []
		for i in t0:
			a.pop(bl(a, c + i))
			t1.append(c + i)
		t1.append(c)
		t0 = t0 + list(t1)
		s.append(c)
	print(*s)


from bisect import bisect_left as bl
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li.sort()
	li.pop(0)
	t0 = []
	s = []
	while li:
		c = li.pop(0)
		t1 = []
		for i in t0:
			li.pop(bl(li, c + i))
			t1.append(c + i)
		t1.append(c)
		t0 += list(t1)
		s.append(c)
	print(*s)


import bisect
tc = int(input())
for _ in range(tc):
	n = int(input())
	s = input().split()
	for i in range(len(s)):
		s[i] = int(s[i])
	a = []
	t = []
	s.sort()
	del s[0]
	while s != []:
		m = s[0]
		del s[0]
		aux = []
		for item1 in a:
			item2 = item1 + m
			index = bisect.bisect_left(s, item2)
			aux.append(item2)
			del s[index]
		aux.append(m)
		a += aux
		t.append(m)
	print(' '.join(map(str, t)))


from collections import defaultdict
import copy
import math

def subsetSums(arr, l, r, dupli_dict, sum=0):
	if l > r:
		dupli_dict[sum] -= 1
		return
	subsetSums(arr, l + 1, r, dupli_dict, sum + arr[l])
	subsetSums(arr, l + 1, r, dupli_dict, sum)
t = int(input())
n = 0
for i in range(t):
	input_dict = defaultdict(int)
	dupli_dict = {}
	n = int(input())
	inp_list = list(map(int, input().strip().split()))[:pow(2, n)]
	for inp in inp_list:
		input_dict[inp] += 1
	dupli_dict = input_dict.copy()
	reconstructed_list = []
	for (k, v) in sorted(input_dict.items()):
		if dupli_dict[k] > 0:
			while dupli_dict[k] > 0:
				if k == 0 and dupli_dict[k] == 1:
					break
				dupli_dict = input_dict.copy()
				reconstructed_list.append(k)
				subsetSums(reconstructed_list, 0, len(reconstructed_list) - 1, dupli_dict)
			if len(reconstructed_list) >= n:
				break
	for r in reconstructed_list:
		print(r, end=' ')
	print()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve(N, arr):
	store = {}
	for ele in arr:
		if ele not in store:
			store[ele] = 1
		else:
			store[ele] += 1
	del store[0]
	final = []
	for ele in store:
		final.append([ele, store[ele]])
	final.sort()
	elements = {}
	tracker = {}
	l = 0
	for array in final:
		ele = array[0]
		count = array[1]
		current = 0
		if l == N:
			break
		while current < count:
			if ele not in tracker:
				elements[ele] = 1
				l += 1
			elif tracker[ele] < count:
				if ele not in elements:
					elements[ele] = 1
				else:
					elements[ele] += 1
				l += 1
			else:
				break
			if l == N:
				break
			temp = {ele: 1}
			for key in tracker:
				count1 = tracker[key]
				val = ele + key
				if val in temp:
					temp[val] += count1
				else:
					temp[val] = count1
			for key in temp:
				if key not in tracker:
					tracker[key] = temp[key]
				else:
					tracker[key] += temp[key]
			current = tracker[ele]
	ans = []
	for key in elements:
		count = elements[key]
		for i in range(count):
			ans.append(key)
	ans.sort()
	sys.stdout.write(' '.join(map(str, ans)) + '\n')
	return
T = get_int()
while T:
	N = get_int()
	arr = get_list()
	solve(N, arr)
	T -= 1


for _ in range(int(input())):
	n = int(input())
	k = 2 ** n
	s = []
	c = []
	r = {}
	a = list(map(int, input().split()))
	a.sort()
	for i in range(1, k):
		if a[i] in r and r[a[i]] != 0:
			r[a[i]] -= 1
		else:
			t = []
			for j in s:
				t.append(j + a[i])
			for j in c:
				t.append(j + a[i])
			for j in t:
				if j not in r:
					r[j] = 0
				r[j] += 1
				s.append(j)
			c.append(a[i])
			if len(c) == n:
				break
	print(*c)


import sys
import math
from collections import defaultdict
import bisect
import heapq

def alele():
	return list(map(int, sys.stdin.readline().strip().split()))

def ilele():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 1000000000 + 7
mark = {}
for _ in range(int(input())):
	N = int(input())
	A = alele()
	mark = {}
	for i in A:
		mark[i] = mark.get(i, 0) + 1
	B = A.copy()
	heapq.heapify(B)
	heapq.heappop(B)
	mark[0] -= 1
	Ans = []
	while len(B) != 0:
		x = heapq.heappop(B)
		while len(B) != 0 and mark.get(x, -1) == 0:
			x = heapq.heappop(B)
		if len(Ans) == N:
			break
		if len(Ans) == 0:
			mark[x] -= 1
		else:
			t = 2 ** len(Ans)
			for j in range(t):
				tot = 0
				for k in range(len(Ans)):
					if j & 1 << k:
						tot += Ans[k]
				mark[tot + x] -= 1
		Ans.append(x)
	print(*Ans)


try:
	from bisect import bisect_left as bl
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		l.sort()
		l.pop(0)
		t0 = []
		s = []
		while l:
			c = l.pop(0)
			t1 = []
			for i in t0:
				l.pop(bl(l, c + i))
				t1.append(c + i)
			t1.append(c)
			t0 += list(t1)
			s.append(c)
		print(*s)
except:
	EOFError


for _ in range(int(input())):
	from bisect import bisect_left as bl
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	ans = []
	arr.pop(0)
	b = []
	while arr:
		x = arr.pop(0)
		temp = [x]
		for ele in b:
			arr.pop(bl(arr, ele + x))
			temp.append(ele + x)
		b += temp
		ans.append(x)
	print(*ans)


from itertools import permutations
from bisect import bisect_left as bl
for __ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li.sort()
	li.pop(0)
	t0 = []
	s = []
	while li:
		t1 = []
		c = li.pop(0)
		for i in t0:
			li.pop(bl(li, c + i))
			t1.append(c + i)
		t1.append(c)
		t0 = t0 + list(t1)
		s.append(c)
	for i in range(n):
		print(s[i], end=' ')
	print()


import heapq
t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	h = []
	a = []
	ans = []
	l.sort()
	l.pop(0)
	for i in range(len(l)):
		exp = -1
		val = l[i]
		if h:
			exp = h[0]
		if exp == val:
			heapq.heappop(h)
		else:
			ans.append(val)
			x = len(a)
			for j in range(x):
				a.append(val + a[j])
				heapq.heappush(h, val + a[j])
			a.append(val)
	print(*ans)
	t -= 1


import heapq
T = int(input())
for z in range(T):
	N = int(input())
	sums = list(map(int, input().split()))
	sums.sort()
	cumm = []
	arr = []
	sums.remove(0)
	heap = []
	for i in range(len(sums)):
		val = sums[i]
		exp = -1
		if heap:
			exp = heap[0]
		if exp == val:
			heapq.heappop(heap)
		else:
			arr.append(val)
			t = len(cumm)
			for i in range(t):
				cumm.append(val + cumm[i])
				heapq.heappush(heap, val + cumm[i])
			cumm.append(val)
	print(*arr)


from collections import deque

def make(a):
	if len(a) == 2:
		print(a[0])
		return
	g = a[0] - a[1]
	print(g, end=' ')
	f = -1
	q = deque()
	b = list()
	for i in a:
		if f < 0 and len(q):
			f = q.pop()
		if i == f:
			b.append(i)
			f = -1
		else:
			q.appendleft(i - g)
	make(b)
for tnum in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a.reverse()
	make(a)


import heapq
for __ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	arr.pop(0)
	pq = []
	bl = []
	ans = []
	for val in arr:
		top = -1
		if len(pq) > 0:
			top = pq[0]
		if top == val:
			heapq.heappop(pq)
		else:
			ans.append(val)
			l = len(bl)
			for i in range(l):
				bl.append(bl[i] + val)
				heapq.heappush(pq, bl[i] + val)
			bl.append(val)
	print(*ans)


from bisect import bisect_left as bl

def subset(ar):
	valueset = []
	ar.pop(0)
	ss = []
	while ar:
		e = ar.pop(0)
		vs = []
		for i in valueset:
			ar.pop(bl(ar, e + i))
			vs.append(e + i)
		vs.append(e)
		valueset += vs
		ss.append(e)
	return ss
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()[:2 ** n]))
	ar.sort()
	print(*subset(ar))


t = int(input())
for _ in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	num.sort()
	sum_arr1 = []
	sum_arr2 = []
	num_arr = [num[1]]
	point = 2
	while len(num_arr) < n:
		if len(num_arr) == 1:
			num_arr.append(num[point])
			sum_arr1.append(num_arr[0] + num[point])
			sum_arr2.append(num_arr[0] + num[point])
		elif num[point] in sum_arr2:
			sum_arr2.remove(num[point])
		else:
			num_arr.append(num[point])
			aa = len(sum_arr1)
			for e in range(len(num_arr) - 1):
				sum_arr1.append(num[point] + num_arr[e])
				sum_arr2.append(num[point] + num_arr[e])
			for f in range(aa):
				sum_arr1.append(sum_arr1[f] + num[point])
				sum_arr2.append(sum_arr1[f] + num[point])
		point += 1
	print(*num_arr)


from collections import OrderedDict
tt = int(input())
for i in range(tt):
	n = int(input())
	d = {}
	a = list(map(int, input().split()))
	for x in a:
		if x == 0:
			continue
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	d = OrderedDict(sorted(d.items()))
	l = [0]
	for i in range(n):
		c = next(iter(d))
		print(c, end=' ')
		l1 = l
		for e in list(l1):
			if d[e + c] == 1:
				del d[e + c]
			else:
				d[e + c] -= 1
			l.append(c + e)
	print()


from heapq import heapify, heappush, heappop
for tt in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s.sort()
	a = []
	h = []
	b = []
	heapify(h)
	s.pop(0)
	for i in range(len(s)):
		if len(h) == 0 or h[0] != s[i]:
			a.append(s[i])
			b.append(s[i])
			for j in range(len(b) - 1):
				heappush(h, b[j] + s[i])
				b.append(s[i] + b[j])
		else:
			heappop(h)
	print(' '.join(map(str, a)))


from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	ans = []
	hp = {}
	dups = {}
	a.sort()
	for i in range(1, len(a)):
		if a[i] in hp and hp[a[i]] > 0:
			hp[a[i]] -= 1
		else:
			new_subsets = []
			for el in dups:
				new_subsets.append((el + a[i], dups[el]))
			for el in ans:
				new_subsets.append((el + a[i], 1))
			for el in new_subsets:
				dups[el[0]] = dups.get(el[0], 0) + el[1]
				hp[el[0]] = hp.get(el[0], 0) + el[1]
			ans.append(a[i])
			if len(ans) == n:
				break
	print(*ans)