# Mahesh and his lost array | CodeChef Solution

Hello coders, today we are going to solve Mahesh and his lost array CodeChef Solution whose Problem Code is ANUMLA.

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 Format

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 Format

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

Sample Input

``````2
1
0 10
2
0 1 1 2
``````

Sample Output

``````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.

## Solution – Mahesh and his lost array

### C++

```#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

#define endl "\n"

#define MOD 1000000007

#define ll long long

int main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output2.txt", "w", stdout);
#endif

ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);

ll t;
cin >> t;

while (t--)
{

ll n;
cin >> n;

multiset<ll>s, new_s;

ll i;

for (i = 0; i < (1 << n); i++)
{

ll x;
cin >> x;
s.insert(x);

}

while (s.size() > 1)
{

ll delta = *(++s.begin());

cout << delta << " ";

while (s.size())
{

multiset<ll>:: iterator i = s.begin();
ll value_i = *i;

s.erase(i);

multiset<ll>:: iterator j = s.find(value_i + delta);
s.erase(j);

new_s.insert(value_i);

}

s.swap(new_s);

}

s.clear();
new_s.clear();

cout << endl;

}

}```

### Python

```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()

```

### Java

```import java.io.*;

import java.util.*;

class A {

public static void main(String[] args) {
int t=sc.nextInt();
PrintWriter out=new PrintWriter(System.out);
while(t-->0) {
int n=sc.nextInt();
int s=(1<<n);
ArrayList<Integer>ans=new ArrayList<>(),removed=new ArrayList<>();
TreeMap<Integer,Integer> map=new TreeMap<>();
for(int i=0;i<s;i++) {
if(a[i]==0)continue;
int c=map.getOrDefault(a[i], 0);
map.put(a[i],++c);
}
while(ans.size()<n) {
int c=map.firstKey(),count=map.get(c);
if(--count>0)map.put(c,count);
else map.remove(c);
//THEN WE TRAVERSE THROUGH ALL REMOVED THINGS AND ADD C TO IT AND REMOVE THOSE
ArrayList<Integer> currRemoval=new ArrayList<>();
for(int e:removed) {
int counts=map.get(e+c);
if(--counts>0)map.put(e+c,counts);
else map.remove(e+c);
}
//UPDATE THE REMOVED LIST
//System.out.println(removed.toString());
}
for(int e:ans)out.print(e+" ");
out.println();

}
out.close();

}

static void reverseSort(int a[]) {
ArrayList<Integer> al=new ArrayList<>();
Collections.sort(al,Collections.reverseOrder());
for(int i=0;i<a.length;i++)a[i]=al.get(i);
}
static int gcd(int a,int b) {
if(b==0)return a;
else return gcd(b,a%b);
}
static long gcd(long a,long b) {
if(b==0)return a;
else return gcd(b,a%b);
}
static void reverse(int a[]) {
int n=a.length;
int b[]=new int[n];
for(int i=0;i<n;i++)b[i]=a[n-1-i];
for(int i=0;i<n;i++)a[i]=b[i];
}
static void reverse(char a[]) {
int n=a.length;
char b[]=new char[n];
for(int i=0;i<n;i++)b[i]=a[n-1-i];
for(int i=0;i<n;i++)a[i]=b[i];
}
static void ruffleSort(int a[]) {
ArrayList<Integer> al=new ArrayList<>();
Collections.sort(al);
for(int i=0;i<a.length;i++)a[i]=al.get(i);
}

static void print(int a[]) {
for(int e:a) {
System.out.print(e+" ");
}
System.out.println();
}
static void print(long a[]) {
for(long e:a) {
System.out.print(e+" ");
}
System.out.println();
}

{
StringTokenizer st;

{
}

String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
}
catch (IOException  e)
{
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt()
{
return Integer.parseInt(next());
}

long nextLong()
{
return Long.parseLong(next());
}

double nextDouble()
{
return Double.parseDouble(next());
}

String nextLine()
{
String str = "";
try
{
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
int a[]=new int [n];
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
}
return a;
}