Given a list arr of N integers, print sums of all subsets in it.
 
Example 1:
Input:
N = 2
arr[] = {2, 3}
Output:
0 2 3 5
Explanation:
When no elements is taken then Sum = 0.
When only 2 is taken then Sum = 2.
When only 3 is taken then Sum = 3.
When element 2 and 3 are taken then 
Sum = 2+3 = 5.
Example 2:
Input:
N = 3
arr = {5, 2, 1}
Output:
0 1 2 3 5 6 7 8
Your Task:  
You don't need to read input or print anything. Your task is to complete the function subsetSums() which takes a list/vector and an integer N as an input parameter and return the list/vector of all the subset sums.
Expected Time Complexity: O(2^{N})
Expected Auxiliary Space: O(2^{N})
Constraints:
1 <= N <= 15
0 <= arr[i] <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3

class Solution:

	def subsetSums(self, arr, N):

		# code here

Solutions:
def subset(i, arr, N, summ, ans):
	if i == N:
		ans.append(summ)
		return
	summ += arr[i]
	subset(i + 1, arr, N, summ, ans)
	summ -= arr[i]
	subset(i + 1, arr, N, summ, ans)

class Solution:

	def subsetSums(self, arr, N):
		ans = []
		summ = 0
		subset(0, arr, N, summ, ans)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		self.ans = []

		def recursive(index, sum_val):
			if index == N:
				self.ans.append(sum_val)
				return
			recursive(index + 1, sum_val + arr[index])
			recursive(index + 1, sum_val)
		recursive(0, 0)
		return self.ans


class Solution:

	def subsetSums(self, arr, N):
		ans = list()

		def sub(i, s):
			if i == N:
				ans.append(s)
				return
			sub(i + 1, s + arr[i])
			sub(i + 1, s)
		sub(0, 0)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		if N == 0:
			return [0]
		if N == 1:
			return [0, arr[0]]
		else:
			pre_arr = self.subsetSums(arr[0:N - 1], N - 1)
			for i in range(2 ** (N - 1)):
				nex = pre_arr[i] + arr[N - 1]
				pre_arr.append(nex)
			return pre_arr


class Solution:

	def subsetSums(self, arr, N):
		res = []

		def helper(arr, res, i, N, sum):
			if i == N:
				res.append(sum)
				return
			helper(arr, res, i + 1, N, sum + arr[i])
			helper(arr, res, i + 1, N, sum)
		helper(arr, res, 0, N, 0)
		res.sort()
		return res


class Solution:

	def subsetSums(self, arr, N):

		def helper(idx, sums, array, res):
			if idx == len(array):
				res.append(sums)
				return
			helper(idx + 1, sums + array[idx], array, res)
			helper(idx + 1, sums, array, res)
		res = []
		helper(0, 0, arr, res)
		return sorted(res)


class Solution:

	def __init__(self):
		self.ans = []

	def helper(self, arr, ind, cur):
		if ind == len(arr):
			self.ans.append(cur)
			return
		self.helper(arr, ind + 1, cur)
		self.helper(arr, ind + 1, cur + arr[ind])

	def subsetSums(self, arr, N):
		self.helper(arr, 0, 0)
		return self.ans


class Solution:

	def subsetSums(self, arr, N):
		sums = [0]

		def rec(arr, index):
			if index == -1:
				return [0]
			else:
				sums.extend([x + arr[index] for x in rec(arr, index - 1)])
				return sums
		return rec(arr, N - 1)


class Solution:

	def solve(self, i, sum1, arr, N, ans):
		if i == N:
			ans.append(sum1)
			return
		sum1 += arr[i]
		self.solve(i + 1, sum1, arr, N, ans)
		sum1 -= arr[i]
		self.solve(i + 1, sum1, arr, N, ans)

	def subsetSums(self, arr, N):
		sum1 = 0
		ans = []
		self.solve(0, sum1, arr, N, ans)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		res = []
		self.s(0, arr, N, 0, res)
		return res

	def s(self, i, arr, n, sum, res):
		if i == n:
			res.append(sum)
			return
		self.s(i + 1, arr, n, sum, res)
		sum += arr[i]
		self.s(i + 1, arr, n, sum, res)


class Solution:

	def subsetSums(self, arr, N):
		l = [[]]
		for i in arr:
			l += [j + [i] for j in l]
		l = [sum(i) for i in l]
		return l


class Solution:

	def subsetSums(self, arr, N):
		res = []

		def f(index, sum, res):
			if index == N:
				res.append(sum)
				return
			sum += arr[index]
			f(index + 1, sum, res)
			sum -= arr[index]
			f(index + 1, sum, res)
		f(0, 0, res)
		return res


class Solution:

	def func(self, i, sum, arr, N, subset):
		if i == N:
			subset.append(sum)
			return
		self.func(i + 1, sum + arr[i], arr, N, subset)
		self.func(i + 1, sum, arr, N, subset)

	def subsetSums(self, arr, N):
		subset = []
		self.func(0, 0, arr, N, subset)
		subset.sort()
		return subset


class Solution:

	def seq(self, subSum, subTup, tup, index, result, i):
		if index < 0:
			result.append(subSum)
			return result
		newSubTup = subTup + (tup[index],)
		self.seq(subSum + tup[index], newSubTup, tup, index - 1, result, i + 1)
		self.seq(subSum, subTup, tup, index - 1, result, i + 1)
		return result

	def subsetSums(self, arr, N):
		result = []
		return list(sorted(self.seq(0, (), tuple(arr), N - 1, result, 0)))


class Solution:

	def subsetSums(self, arr, N):

		def find(arr, ind, output, sum=0):
			if len(arr) == ind:
				output.append(sum)
				return
			find(arr, ind + 1, output, sum + arr[ind])
			find(arr, ind + 1, output, sum)
		output = []
		find(arr, 0, output)
		return output


class Solution:

	def subsetSums(self, arr, N):
		s = 0
		ans = []

		def f(i, s):
			if i == N:
				ans.append(s)
				return
			f(i + 1, s + arr[i])
			f(i + 1, s)
		f(0, s)
		return ans


ans = []

def solve(l, n, i, s):
	global ans
	if i == n:
		ans.append(s)
		return
	solve(l, n, i + 1, s)
	solve(l, n, i + 1, s + l[i])

class Solution:

	def subsetSums(self, arr, N):
		global ans
		ans = []
		solve(arr, N, 0, 0)
		return ans


class Solution:

	def subseq(self, i, arr, ds, container):
		if i == len(arr):
			nums = [i for i in ds]
			nums.sort()
			container.append(nums)
			return
		if i < len(arr):
			ds.append(arr[i])
			self.subseq(i + 1, arr, ds, container)
			ds.pop()
			self.subseq(i + 1, arr, ds, container)

	def subsetSums(self, arr, N):
		ds = []
		container = []
		i = 0
		self.subseq(i, arr, ds, container)
		res = []
		for i in container:
			res.append(sum(i))
		return res


class Solution:

	def subsetSums(self, arr, N):
		path = []

		def dfs(ind, sums):
			if ind == N:
				path.append(sums)
				return
			dfs(ind + 1, sums + arr[ind])
			dfs(ind + 1, sums)
		dfs(0, 0)
		return path


class Solution:

	def subsetSums(self, a, N):

		def dfs(i, sum, ans):
			if i == len(a):
				ans.append(sum)
				return
			dfs(i + 1, sum + a[i], ans)
			dfs(i + 1, sum, ans)
		ans = []
		dfs(0, 0, ans)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		ans = []
		self.helper(arr, N, 0, ans, 0)
		return ans

	def helper(self, arr, N, index, ans, s):
		if index == N:
			ans.append(s)
			return
		self.helper(arr, N, index + 1, ans, s + arr[index])
		self.helper(arr, N, index + 1, ans, s)


class Solution:

	def helper(self, arr, N, i, ans, total=0):
		if i == N:
			ans.append(total)
			return
		self.helper(arr, N, i + 1, ans, total + arr[i])
		self.helper(arr, N, i + 1, ans, total)

	def subsetSums(self, arr, N):
		total = 0
		ans = []
		self.helper(arr, N, 0, ans, total)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		ans = []

		def subsetSumHelper(ind, sum):
			if ind == N:
				ans.append(sum)
				return
			subsetSumHelper(ind + 1, sum + arr[ind])
			subsetSumHelper(ind + 1, sum)
		subsetSumHelper(0, 0)
		ans.sort()
		return ans


class Solution:

	def subsetSums(self, arr, N):
		ans = []

		def subsetSumsHelper(ind: int, sum: int):
			if ind == N:
				ans.append(sum)
				return
			subsetSumsHelper(ind + 1, sum + arr[ind])
			subsetSumsHelper(ind + 1, sum)
		subsetSumsHelper(0, 0)
		ans.sort()
		return ans


class Solution:

	def subsetSums(self, arr, N):

		def function(i, sum, arr, N, sumsubset):
			if i == N:
				sumsubset.append(sum)
				return
			function(i + 1, sum + arr[i], arr, N, sumsubset)
			function(i + 1, sum, arr, N, sumsubset)
		sumsubset = []
		function(0, 0, arr, N, sumsubset)
		sumsubset.sort()
		return sumsubset


class Solution:

	def subsetSums(self, arr, N):
		res = []
		sumer = 0

		def bt(index):
			nonlocal sumer
			if index >= len(arr):
				res.append(sumer)
				return
			sumer += arr[index]
			bt(index + 1)
			sumer -= arr[index]
			bt(index + 1)
		bt(0)
		res.sort()
		return res


class Solution:

	def subsetSums(self, arr, N):
		sums = []
		run_sum = 0
		self.helper(arr, N, run_sum, sums)
		return sums

	def helper(self, arr, N, run_sum, sums):
		if N == 0:
			sums.append(run_sum)
			return
		self.helper(arr, N - 1, run_sum + arr[N - 1], sums)
		self.helper(arr, N - 1, run_sum, sums)
		return


class Solution:

	def subsetSums(self, nums, N):
		ans = []

		def subset(p, up):
			if len(up) == 0:
				ans.append(p)
				return
			ch = up[0]
			subset(p + [ch], up[1:])
			subset(p, up[1:])
		subset([], nums)
		res = [sum(sub) for sub in ans]
		return res


class Solution:

	def subsetSums(self, arr, N):

		def backtracking(index, currSum):
			if index == N:
				result.append(currSum)
				return
			backtracking(index + 1, currSum + arr[index])
			backtracking(index + 1, currSum)
		result = []
		backtracking(0, 0)
		return result


class Solution:

	def subsum(self, arr, index, N, sumsofar):
		if index == N:
			self.res.append(sumsofar)
			return
		self.subsum(arr, index + 1, N, sumsofar + arr[index])
		self.subsum(arr, index + 1, N, sumsofar)

	def subsetSums(self, arr, N):
		self.res = []
		self.subsum(arr, 0, N, 0)
		return self.res


class Solution:

	def subsetSums(self, arr, N):

		def rec(arr, n, sum1, l):
			if n < 0:
				l.append(sum1)
				return
			rec(arr, n - 1, sum1 + arr[n], l)
			rec(arr, n - 1, sum1, l)
		l = []
		rec(arr, N - 1, 0, l)
		return l


class Solution:

	def subsetSums(self, arr, N):

		def subset(ind, summ, sumset):
			if ind == N:
				sumset.append(summ)
				return
			subset(ind + 1, summ + arr[ind], sumset)
			subset(ind + 1, summ, sumset)
		summ = 0
		sumset = []
		subset(0, summ, sumset)
		return sumset


class Solution:

	def subsetSums(self, arr, N):

		def rec(idx, sm):
			if idx >= N:
				return [sm]
			return rec(idx + 1, arr[idx] + sm) + rec(idx + 1, sm)
		return rec(0, 0)


class Solution:

	def subsetSums(self, arr, N):
		final = []

		def recursion(index, subset, arr, N, final):
			if len(subset) == N or index >= N:
				final.append(sum(subset))
				return
			recursion(index + 1, subset + [arr[index]], arr, N, final)
			recursion(index + 1, subset, arr, N, final)
		recursion(0, [], arr, N, final)
		return final


class Solution:

	def subsetSums(self, arr, N):
		ans = []
		n = len(arr)
		for i in range(1 << n):
			l = [arr[j] for j in range(n) if i & 1 << j]
			ans.append(sum(l))
		return ans


class Solution:

	def subsetSums(self, arr, N):
		ans = []
		n = len(arr)

		def fun(arr, s, ind):
			if ind == n:
				ans.append(s)
				return
			fun(arr, s + arr[ind], ind + 1)
			fun(arr, s, ind + 1)
		fun(arr, 0, 0)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		res = []

		def dfs(ind, subsum):
			if ind == N:
				res.append(subsum)
				return
			dfs(ind + 1, subsum + arr[ind])
			dfs(ind + 1, subsum)
		dfs(0, 0)
		return res


class Solution:

	def _subsetSums(self, ind, arr, N, ans, summ):
		if ind == N:
			ans.append(summ)
			return
		self._subsetSums(ind + 1, arr, N, ans, summ + arr[ind])
		self._subsetSums(ind + 1, arr, N, ans, summ)

	def subsetSums(self, arr, N):
		ans = []
		self._subsetSums(0, arr, N, ans, 0)
		return ans


from itertools import combinations

class Solution:

	def solve(self, arr, sum=0, pointer=0, left=True):
		if left:
			self.returnlis.append(sum)
		if len(arr) == 0 or pointer >= self.length:
			return
		take = self.solve(arr[1:], sum + arr[0], pointer + 1, True)
		skip = self.solve(arr[1:], sum, pointer + 1, False)
		return

	def subsetSums(self, arr, N):
		self.returnlis = []
		for i in range(N + 1):
			for j in combinations(arr, i):
				self.returnlis.append(sum(j))
		return sorted(self.returnlis)


from itertools import chain, combinations

class Solution:

	def subsetSums(self, arr, N):
		ans = []
		combs = chain.from_iterable((combinations(arr, r) for r in range(N + 1)))
		for c in combs:
			ans.append(sum(c))
		return ans


class Solution:

	def helper(self, ind, s, arr, ans):
		if ind == len(arr):
			ans.append(s)
			return
		self.helper(ind + 1, s + arr[ind], arr, ans)
		self.helper(ind + 1, s, arr, ans)

	def subsetSums(self, arr, N):
		ans = []
		self.helper(0, 0, arr, ans)
		ans.sort()
		return ans


class Solution:

	def solve(self, arr, sum=0, pointer=0, left=True):
		if left:
			self.returnlis.append(sum)
		if len(arr) == 0 or pointer >= self.length:
			return
		take = self.solve(arr[1:], sum + arr[0], pointer + 1, True)
		skip = self.solve(arr[1:], sum, pointer + 1, False)
		return

	def subsetSums(self, arr, N):
		self.returnlis = []
		self.length = len(arr)
		if self.length == 1:
			return [0, arr[0]]
		if self.length == 0:
			return [0]
		arr.sort()
		self.solve(arr)
		return sorted(self.returnlis)


class Solution:

	def subsetSums(self, arr, N):
		subset_sums = []
		for i in range(2 ** N):
			current_sum = 0
			for j in range(N):
				if i & 1 << j:
					current_sum += arr[j]
			subset_sums.append(current_sum)
		subset_sums.sort()
		return subset_sums


class Solution:

	def subsetSums(self, arr, N):

		def dfs(curr_sum, i):
			if i >= len(arr):
				res.append(curr_sum)
				return
			dfs(curr_sum, i + 1)
			dfs(curr_sum + arr[i], i + 1)
		res = []
		dfs(0, 0)
		return res


class Solution:

	def getSumSubsets(self, arr, currIdx, currentSum, ans, N):
		if currIdx == N:
			ans.append(currentSum)
			return
		self.getSumSubsets(arr, currIdx + 1, currentSum + arr[currIdx], ans, N)
		self.getSumSubsets(arr, currIdx + 1, currentSum, ans, N)
		return

	def subsetSums(self, arr, N):
		ans = []
		self.getSumSubsets(arr, 0, 0, ans, N)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		ans = []

		def subsetsumshelper(ind, x):
			if ind == N:
				ans.append(x)
				return
			subsetsumshelper(ind + 1, x + arr[ind])
			subsetsumshelper(ind + 1, x)
		subsetsumshelper(0, 0)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		sum = 0
		ans = []

		def recursive(arr, sum, index, ans):
			if index == len(arr):
				ans.append(sum)
				return
			recursive(arr, sum + arr[index], index + 1, ans)
			recursive(arr, sum, index + 1, ans)
		recursive(arr, sum, 0, ans)
		return ans


class Solution:

	def calc(self, currSum, i):
		if i >= len(self.arr):
			return
		self.ans.append(currSum + self.arr[i])
		self.calc(currSum + self.arr[i], i + 1)
		self.calc(currSum, i + 1)

	def subsetSums(self, arr, N):
		self.arr = arr
		self.ans = [0]
		self.calc(0, 0)
		return self.ans


def helper(arr, index, subarr, result):
	if index >= len(arr):
		result.append(sum(subarr))
		return
	subarr.append(arr[index])
	helper(arr, index + 1, subarr, result)
	subarr.remove(arr[index])
	helper(arr, index + 1, subarr, result)

class Solution:

	def subsetSums(self, arr, N):
		res = []
		helper(arr, 0, [], res)
		return res


class Solution:

	def subsetSums(self, arr, N):
		a = []

		def sub(i, s):
			if i == N:
				a.append(s)
				return
			sub(i + 1, s + arr[i])
			sub(i + 1, s)
		sub(0, 0)
		a.sort()
		return a


class Solution:

	def subsetSums(self, arr, N):
		res = []

		def ans(idx, arr, sum, res):
			if idx == len(arr):
				res.append(sum)
				return
			ans(idx + 1, arr, sum + arr[idx], res)
			ans(idx + 1, arr, sum, res)
		ans(0, arr, 0, res)
		return res


class Solution:

	def subsetSums(self, arr, N):

		def generateSubsets(index, subsetSum):
			if index == N:
				subsetSums.append(subsetSum)
				return
			generateSubsets(index + 1, subsetSum)
			generateSubsets(index + 1, subsetSum + arr[index])
		subsetSums = []
		generateSubsets(0, 0)
		return subsetSums


class Solution:

	def subsetSums(self, arr, N):

		def solve(i, arr, ans, s):
			if i >= len(arr):
				ans.append(s)
				return
			solve(i + 1, arr, ans, s + arr[i])
			solve(i + 1, arr, ans, s)
		ans = []
		s = 0
		solve(0, arr, ans, s)
		ans.sort()
		return ans


class Solution:

	def subsetSums(self, arr, N):
		ans = []

		def helper(index, sums):
			if index == N:
				ans.append(sums)
				return
			helper(index + 1, sums + arr[index])
			helper(index + 1, sums)
		helper(0, 0)
		ans.sort()
		return ans


class Solution:

	def subsetSums(self, arr, N):
		ans = []

		def getAns(i, su, ans):
			if i == N:
				ans.append(su)
				return
			getAns(i + 1, su + arr[i], ans)
			getAns(i + 1, su, ans)
		getAns(0, 0, ans)
		return ans


class Solution:

	def subsetSums(self, arr, N):

		def recursion(index, ds, output):
			if index == N:
				output.append(sum(ds))
				return
			ds.append(arr[index])
			recursion(index + 1, ds, output)
			ds.pop()
			recursion(index + 1, ds, output)
			return
		(out, ds) = ([], [])
		recursion(0, ds, out)
		out.sort()
		return out


class Solution:

	def solve(self, idx, arr, summ, ans):
		if idx >= len(arr):
			ans.append(summ)
			return
		self.solve(idx + 1, arr, summ + arr[idx], ans)
		self.solve(idx + 1, arr, summ, ans)

	def subsetSums(self, arr, N):
		ans = []
		self.solve(0, arr, 0, ans)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		l = []

		def sub(i, arr, sum, N, l):
			if i == len(arr):
				l.append(sum)
				return
			sub(i + 1, arr, sum + arr[i], N, l)
			sub(i + 1, arr, sum, N, l)
		sub(0, arr, 0, N, l)
		l.sort()
		return l


class Solution:

	def subsetSums(self, arr, N):
		result = []
		self.helper(0, 0, arr, result)
		return sorted(result)

	def helper(self, index, sum, arr, result):
		if index == len(arr):
			result.append(sum)
			return
		self.helper(index + 1, sum + arr[index], arr, result)
		self.helper(index + 1, sum, arr, result)


class Solution:

	def subsetSums(self, arr, N):
		result = []
		self.subset(0, 0, arr, N, result)
		return result

	def subset(self, i, summ, arr, n, result):
		if i >= n:
			result.append(summ)
			return
		summ += arr[i]
		self.subset(i + 1, summ, arr, n, result)
		summ -= arr[i]
		self.subset(i + 1, summ, arr, n, result)


class Solution:

	def subsetRecur(self, arr, vis, S, ans, N):
		ans.append(S)
		for i in range(N):
			if not vis[i]:
				vis[i] = True
				self.subsetRecur(arr, vis.copy(), S - arr[i], ans, N)

	def subsetSums(self, arr, N):
		S = sum(arr)
		vis = [False] * N
		ans = []
		self.subsetRecur(arr, vis, S, ans, N)
		return ans


def subset_sum(idx, arr, n, sum, res):
	if idx == n:
		res.append(sum)
		return
	sum += arr[idx]
	subset_sum(idx + 1, arr, n, sum, res)
	sum -= arr[idx]
	subset_sum(idx + 1, arr, n, sum, res)

class Solution:

	def subsetSums(self, arr, N):
		res = []
		subset_sum(0, arr, N, 0, res)
		return sorted(res)


class Solution:

	def subsetSums(self, arr, N):
		res = [[]]
		for i in arr:
			res += [[i] + lst for lst in res]
		lst = list(map(sum, res))
		return lst


class Solution:

	def subsetSums(self, arr, N):
		sub = [0]
		for i in range(N):
			m = len(sub)
			for j in range(m):
				sub.append(sub[j] + arr[i])
		return sub


class Solution:

	def subsetSums(self, arr, N):
		subset_sums = []

		def helper(index, sum):
			if index == N:
				subset_sums.append(sum)
				return
			helper(index + 1, sum + arr[index])
			helper(index + 1, sum)
			return
		helper(0, 0)
		return subset_sums


class Solution:

	def subsetSums(self, arr, N):

		def recur(ind, sm):
			if ind == N:
				ans.append(sm)
				return
			recur(ind + 1, sm + arr[ind])
			recur(ind + 1, sm)
		ans = []
		recur(0, 0)
		return ans


class Solution:

	def subsetSums(self, nums, N):
		ans = []

		def findSubsets(ind, target):
			ans.append(target)
			for i in range(ind, len(nums)):
				findSubsets(i + 1, target + nums[i])
		nums.sort()
		findSubsets(0, 0)
		return ans


from itertools import combinations

class Solution:

	def subsetSums(self, arr, N):
		com = []
		li = []
		for i in range(len(arr) + 1):
			com = [sum(j) for j in combinations(arr, i)]
			for j in com:
				li.append(j)
		return li


class Solution:

	def gen(self, arr, n, ans, suma):
		if n == 0:
			ans.append(suma)
			return
		self.gen(arr, n - 1, ans, suma + arr[n - 1])
		self.gen(arr, n - 1, ans, suma)

	def subsetSums(self, arr, n):
		ans = []
		self.gen(arr, n, ans, 0)
		return sorted(ans)


class Solution:

	def find(self, i, sum, arr, ans):
		if i == len(arr):
			ans.append(sum)
			return
		sum += arr[i]
		self.find(i + 1, sum, arr, ans)
		sum -= arr[i]
		self.find(i + 1, sum, arr, ans)

	def subsetSums(self, arr, N):
		ans = []
		self.find(0, 0, arr, ans)
		return ans


class Solution:

	def subsets(self, idx, arr, sum_val, N, L):
		if idx == N:
			L.append(sum_val)
			return L
		self.subsets(idx + 1, arr, sum_val + arr[idx], N, L)
		return self.subsets(idx + 1, arr, sum_val, N, L)

	def subsetSums(self, arr, N):
		L = []
		x = self.subsets(0, arr, 0, N, L)
		L.sort()
		return L


class Solution:

	def subsetSums(self, arr, N):
		res = []
		for i in range(1 << N):
			sum = 0
			for j in range(N):
				if i & 1 << j:
					sum += arr[j]
			res.append(sum)
		res.sort()
		return res


class Solution:

	def subsetSums(self, n, N):
		a = []

		def s(i, c):
			if i >= N:
				a.append(c)
				return
			s(i + 1, c + n[i])
			s(i + 1, c)
		s(0, 0)
		a.sort()
		return a


class Solution:

	def subsetSums(self, arr, N):
		result = []
		op = []

		def createSubsets(ip, op, i):
			if i == len(ip):
				result.append(sum(op[:]))
				return
			createSubsets(ip, op, i + 1)
			op.append(ip[i])
			createSubsets(ip, op, i + 1)
			op.pop(len(op) - 1)
		createSubsets(arr, op, 0)
		return result


class Solution:

	def solve(self, ind, arr, n, ans, suma):
		if ind == n:
			ans.append(suma)
			return
		self.solve(ind + 1, arr, n, ans, suma + arr[ind])
		self.solve(ind + 1, arr, n, ans, suma)

	def subsetSums(self, arr, N):
		ans = []
		self.solve(0, arr, N, ans, 0)
		return ans


class Solution:

	def subsetSums(self, arr, N):
		a = 0
		sol = []
		arr.sort()

		def pt(i, a):
			if i == N:
				sol.append(a)
				return
			a += arr[i]
			pt(i + 1, a)
			a -= arr[i]
			pt(i + 1, a)
		pt(0, a)
		return sol


class Solution:

	def subsetSums(self, arr, N):
		self.res = []

		def solve(i, N, arr, sum, ans):
			if N == i:
				ans.append(sum)
				return
			solve(i + 1, N, arr, sum + arr[i], ans)
			solve(i + 1, N, arr, sum, ans)
		solve(0, N, arr, 0, self.res)
		return self.res


class Solution:

	def subsetSums(self, arr, N):
		final = []
		self.rec(arr, N, final, 0, [])
		return final

	def rec(self, arr, N, final, i, b):
		if i == N:
			final.append(sum(b))
			return
		b.append(arr[i])
		self.rec(arr, N, final, i + 1, b)
		b.pop()
		self.rec(arr, N, final, i + 1, b)


class Solution:

	def subsetSums(self, arr, N):
		n = len(arr)
		subsets = []
		lst = []
		for i in range(2 ** n):
			subset = []
			for j in range(n):
				if i & 1 << j:
					subset.append(arr[j])
			subsets.append(subset)
		for k in subsets:
			lst.append(sum(k))
		return lst


class Solution:

	def subsetSums(self, arr, N):

		def solve(ip, op, target, ans):
			if len(ip) == 0:
				ans.append(target)
				return ans
			op1 = op[:]
			op2 = op[:]
			op2.append(ip[0])
			target1 = target
			target2 = target + ip[0]
			ip = ip[1:]
			solve(ip, op1, target1, ans)
			solve(ip, op2, target2, ans)
			return ans
		ans = []
		op = []
		target = 0
		ans = solve(arr, op, target, ans)
		return sorted(ans)


class Solution:

	def solve(self, i, sum, ans, arr, n):
		if i == n:
			ans.append(sum)
			return
		self.solve(i + 1, sum + arr[i], ans, arr, n)
		self.solve(i + 1, sum, ans, arr, n)

	def subsetSums(self, arr, n):
		ans = []
		self.solve(0, 0, ans, arr, n)
		ans.sort()
		return ans


a = [0]

class Solution:

	def subsetSums(self, arr, N):
		xxx = func(arr, N, 0, N - 1, [], 0)
		return xxx

def func(arr, N, l, r, xx, summ):
	if l > r:
		xx.append(summ)
		return
	s1 = func(arr, N, l + 1, r, xx, summ + arr[l])
	s2 = func(arr, N, l + 1, r, xx, summ)
	return xx


class Solution:

	def rec(self, i, arr, lst, sm, present):
		if i < 0:
			if present == False:
				lst.append(sm)
			return 0
		if present == False:
			lst.append(sm)
		self.rec(i - 1, arr, lst, sm + arr[i], False)
		self.rec(i - 1, arr, lst, sm, True)
		return

	def subsetSums(self, arr, N):
		lst = []
		self.rec(N - 1, arr, lst, 0, False)
		return lst