Given a set of integers, find all distinct sums that can be generated from the subsets of the given sets.
 
Example 1:
Input: nums = {1,2}
Output: {0,1,2,3}
Explanation: Four distinct sums can be
calculated which are 0, 1, 2 and 3.
0 if we do not choose any number.
1 if we choose only 1.
2 if we choose only 2.
3 if we choose 1 and 2.
Example 2:
Input: nums = {1,2,3}
Output: {0,1,2,3,4,5,6}
Explanation: Seven distinct sum can be calculated
which are 0, 1, 2, 3, 4, 5 and 6.
0 if we do not choose any number.
1 if we choose only 1.
2 if we choose only 2.
3 if we choose only 3.
4 if we choose 1 and 3.
5 if we choose 2 and 3.
6 if we choose 1, 2 and 3.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function DistinictSum() which takes nums as input parameter and returns a list containing the distinict sum in increasing order,
 
Expected Time Complexity: O(n * sum) where sum = sum of all elements of nums.
Expected Space Complexity: O(n * sum)
 
Constraints:
1 <= length of nums <= 10^{2}
1 <= nums[i] <= 10^{2}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def DistinctSum(self, nums):

		# Code here

Solutions:
class Solution:

	def DistinctSum(self, nums):
		sums = {0}
		for x in nums:
			sums.update([s + x for s in sums])
		return sorted(sums)


class Solution:

	def DistinctSum(self, nums):
		distinct_sums = set()
		prev_sums = {0}
		for num in nums:
			curr_sums = set()
			for prev_sum in prev_sums:
				curr_sum = num + prev_sum
				curr_sums.add(curr_sum)
				distinct_sums.add(curr_sum)
			prev_sums.update(curr_sums)
		distinct_sums = list(sorted(distinct_sums))
		if 0 not in distinct_sums:
			distinct_sums = [0] + distinct_sums
		return distinct_sums


class Solution:

	def DistinctSum(self, nums):
		s = sum(nums)
		dp = [[False for i in range(s + 1)] for j in range(len(nums) + 1)]
		for i in range(len(nums) + 1):
			dp[i][0] = True
		for i in range(1, len(nums) + 1):
			for j in range(1, s + 1):
				if nums[i - 1] <= j:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
				else:
					dp[i][j] = dp[i - 1][j]
		res = []
		for i in range(s + 1):
			if dp[-1][i]:
				res.append(i)
		return res

		def sub(i, ans):
			if i == len(nums):
				return {sum(ans)}
			return sub(i + 1, ans + [nums[i]]).union(sub(i + 1, ans))
		return sorted(list(sub(0, [])))


from collections import defaultdict

class Solution:

	def recur(self, i, sm, nums):
		if (i, sm) in self.memo:
			return
		self.result[sm] = 1
		if i >= len(nums):
			return
		self.recur(i + 1, sm, nums)
		self.recur(i + 1, sm + nums[i], nums)
		self.memo[i, sm] = 1

	def DistinctSum(self, nums):
		nums.sort()
		self.result = {}
		self.memo = {}
		self.recur(0, 0, nums)
		return sorted(list(self.result))


class Solution:

	def DistinctSum(self, nums):
		s = sum(nums)
		n = len(nums)
		dp = [[0 for i in range(s + 1)] for j in range(n)]
		for i in range(n):
			for j in range(s + 1):
				if j == 0:
					dp[i][j] = 1
				elif i == 0:
					dp[i][j] = 1 if j == nums[i] else 0
				elif nums[i] <= j:
					dp[i][j] = dp[i - 1][j - nums[i]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		res = []
		for i in range(s + 1):
			if dp[n - 1][i]:
				res.append(i)
		return res


class Solution:

	def DistinctSum(self, nums):
		dp = [[0 for _ in range(10001)] for _ in range(len(nums))]
		s = set()

		def sol(i, arr, s, sum):
			if i == len(arr):
				s.add(sum)
				return
			if dp[i][sum]:
				return
			sol(i + 1, arr, s, sum)
			sol(i + 1, arr, s, sum + arr[i])
			dp[i][sum] = 1
		sol(0, nums, s, 0)
		return sorted(s)


class Solution:

	def DistinctSum(self, nums):
		s = sum(nums)
		n = len(nums)
		t = [[0 for i in range(s + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			t[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, s + 1):
				if nums[i - 1] <= j:
					t[i][j] = t[i - 1][j - nums[i - 1]] or t[i - 1][j]
				else:
					t[i][j] = t[i - 1][j]
		l = []
		for i in range(s + 1):
			if t[n][i]:
				l.append(i)
		return l


class Solution:

	def DistinctSum(self, nums):
		ans = [0]
		t = sum(nums)
		n = len(nums)
		nums.sort()
		dp = [[0 for i in range(n + 1)] for j in range(t + 1)]
		for i in range(1, t + 1):
			for j in range(1, n + 1):
				if i == nums[j - 1]:
					dp[i][j] = 1
				elif i < nums[j - 1]:
					dp[i][j] = dp[i][j - 1]
				else:
					dp[i][j] = max(dp[i - nums[j - 1]][j - 1], dp[i][j - 1])
			if dp[i][n]:
				ans.append(i)
		return ans


class Solution:

	def DistinctSum(self, nums):
		dp = [False] * (sum(nums) + 1)
		dp[0] = True
		for e in nums:
			temp = dp.copy()
			for s in range(1, sum(nums) + 1):
				if e <= s:
					temp[s] = dp[s] or dp[s - e]
			dp = temp
		res = []
		for i in range(sum(nums) + 1):
			if dp[i]:
				res.append(i)
		return res


class Solution:

	def DistinctSum(self, nums):
		l = []
		arr = nums
		Sum = sum(arr)
		dp = [[False for i in range(Sum + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			dp[i][arr[i - 1]] = True
			for j in range(1, Sum + 1):
				if dp[i - 1][j] == True:
					dp[i][j] = True
					dp[i][j + arr[i - 1]] = True
		for j in range(Sum + 1):
			if dp[n][j] == True:
				l.append(j)
		return l


class Solution:

	def DistinctSum(self, nums):
		nums.sort()
		mask = 1
		for i in nums:
			mask |= mask << i
		mask = bin(mask)[2:]
		mask = mask[::-1]
		n = len(mask)
		l = []
		for i in range(n):
			if mask[i] == '1':
				l.append(i)
		return l


class Solution:

	def DistinctSum(self, nums):
		total = sum(nums) + 1
		n = len(nums) + 1
		dp = [[False] * total for __ in range(n)]
		vis = [False] * total
		vis[0] = True
		for i in range(n):
			dp[i][0] = True
		for i in range(1, n):
			for j in range(1, total):
				if nums[i - 1] > j:
					dp[i][j] = dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
					if dp[i][j] and (not vis[j]):
						vis[j] = True
		res = [i for i in range(total) if vis[i]]
		return res


class Solution:

	def DistinctSum(self, nums):
		n = len(nums)
		total = sum(nums)
		res = []
		dp = [[False] * (sum(nums) + 1) for row in range(n + 1)]
		nums.insert(0, 0)
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			dp[i][nums[i]] = True
			for j in range(1, total + 1):
				if dp[i - 1][j]:
					dp[i][j] = True
					dp[i][j + nums[i]] = True
		for i in range(total + 1):
			if dp[n][i]:
				res.append(i)
		return res


class Solution:

	def DistinctSum(self, nums):
		SUM = sum(nums)
		n = len(nums)
		dp = [[0 for j in range(SUM + 1)] for i in range(n + 1)]
		ans = set()

		def solve(i, csum):
			if i == n:
				ans.add(csum)
				return
			if dp[i][csum] != 0:
				return
			dp[i][csum] = -1
			solve(i + 1, csum)
			solve(i + 1, csum + nums[i])
		solve(0, 0)
		ans = list(ans)
		ans.sort()
		return ans


class Solution:

	def DistinctSum(self, nums):
		ans = set()
		(n, Tsum) = (len(nums), sum(nums))
		dp = [[-1 for i in range(Tsum + 1)] for i in range(n + 1)]

		def recursive(nums, n, curSum=0):
			nonlocal ans
			if n == 0:
				ans.add(curSum)
				return 1
			if dp[n][curSum] != -1:
				return
			recursive(nums, n - 1, curSum)
			recursive(nums, n - 1, curSum + nums[n - 1])
			dp[n][curSum] = 1
			return
		recursive(nums, n)
		return sorted(ans)


class Solution:

	def DistinctSum(self, nums):
		m = set()
		dp = {}

		def dfs(i, s):
			if i == len(nums):
				m.add(s)
				return
			if (i, s) in dp:
				return
			dp[i, s] = 1
			dfs(i + 1, s + nums[i])
			dfs(i + 1, s)
		dfs(0, 0)
		l = []
		for i in m:
			l.append(i)
		l.sort()
		return l


class Solution:

	def DistinctSum(self, A):
		N = len(A)
		summ = sum(A)
		ans = []
		dp = [[False for i in range(summ + 1)] for i in range(N + 1)]
		for i in range(N + 1):
			dp[i][0] = True
		for i in range(1, N + 1):
			dp[i][A[i - 1]] = True
			for j in range(1, summ + 1):
				dp[i][j] |= dp[i - 1][j]
				if dp[i - 1][j]:
					dp[i][j + A[i - 1]] = True
		for i in range(summ + 1):
			if dp[-1][i]:
				ans.append(i)
		return ans


class Solution:

	def DistinctSum(self, x):
		se = {0}
		for i in x:
			q = set()
			for j in se:
				q.add(j + i)
			se = se.union(q)
		return sorted(se)


class Solution:

	def DistinctSum(self, nums):
		dp = {}
		L = len(nums)

		def solve(i):
			if i == L:
				return [0]
			elif i in dp:
				return dp[i]
			else:
				a = solve(i + 1)
				nxt_a = [x + nums[i] for x in a]
				nxt_a.extend(a)
				dp[i] = list(set(nxt_a))
				return dp[i]
		return sorted(solve(0))


class Solution:

	def rec(self, i, tm, nums):
		if (i, tm) in self.memo:
			return
		self.result.add(tm)
		if i >= len(nums):
			return
		self.rec(i + 1, tm, nums)
		self.rec(i + 1, tm + nums[i], nums)
		self.memo[i, tm] = 1

	def DistinctSum(self, nums):
		nums.sort()
		self.memo = {}
		self.result = set()
		self.rec(0, 0, nums)
		return sorted(list(self.result))


class Solution:

	def DistinctSum(self, nums):
		n = len(nums)
		sum = 0
		arr = []
		for i in nums:
			sum += i
		dp = [[False for i in range(sum + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, sum + 1):
				notpick = dp[i - 1][j]
				pick = False
				if nums[i - 1] <= j:
					pick = dp[i - 1][j - nums[i - 1]]
				dp[i][j] = pick | notpick
		for i in range(sum + 1):
			if dp[n][i] == True:
				arr.append(i)
		return arr


class Solution:

	def DistinctSum(self, nums):
		sm = 0
		n = len(nums)
		for ele in nums:
			sm += ele
		dp = [[0] * (sm + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			for j in range(1, sm + 1):
				if nums[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - nums[i - 1]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		ans = []
		for i in range(sm + 1):
			if dp[n][i]:
				ans += [i]
		return ans


class Solution:

	def DistinctSum(self, nums):
		res = set()
		dp = [[-1 for i in range(sum(nums) + 1)] for j in range(len(nums) + 1)]

		def dfs(i, sums):
			if i == len(nums):
				res.add(sums)
				return
			if dp[i][sums] != -1:
				return
			dfs(i + 1, sums)
			dfs(i + 1, sums + nums[i])
			dp[i][sums] = 1
		dfs(0, 0)
		ans = list(res)
		ans.sort()
		return ans


class Solution:

	def recur(self, i, sm, nums):
		if (i, sm) in self.memo:
			return
		self.result[sm] = 1
		if i >= len(nums):
			return
		self.recur(i + 1, sm, nums)
		self.recur(i + 1, sm + nums[i], nums)
		self.memo[i, sm] = 1

	def DistinctSum(self, nums):
		nums.sort()
		self.result = {}
		self.memo = {}
		self.recur(0, 0, nums)
		return sorted(list(self.result))
		n = len(nums)
		dp = [0] * 2
		dp[1] = nums[0]
		for i in range(1, n):
			j = 0
			temp = []
			while j < len(dp):
				sum_ = dp[j] + nums[i]
				if sum_ not in dp:
					temp.append(sum_)
				j += 1
			dp += temp
		dp.sort()
		return dp


class Solution:

	def DistinctSum(self, nums):
		s = {0}
		for i in nums:
			s.update([i + j for j in s])
		return sorted(s)


class Solution:

	def DistinctSum(self, nums):
		n = len(nums)
		m = sum(nums)
		dp = [[False for i in range(m + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			for j in range(m + 1):
				if j == 0:
					dp[i][j] = True
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if nums[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - nums[i - 1]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		s = set()
		for i in range(n + 1):
			for j in range(m + 1):
				if dp[i][j]:
					s.add(j)
		return sorted(list(s))


class Solution:

	def DistinctSum(self, nums):
		ans = set()
		ans.add(0)
		for num in nums:
			a = []
			for r in ans:
				a.append(r + num)
			ans.update(a)
		return sorted(list(ans))


class Solution:

	def recur(self, i, sm, nums):
		if (i, sm) in self.memo:
			return
		self.result.add(sm)
		if i >= len(nums):
			return
		self.recur(i + 1, sm, nums)
		self.recur(i + 1, sm + nums[i], nums)
		self.memo[i, sm] = 1

	def DistinctSum(self, nums):
		nums.sort()
		self.result = set()
		self.memo = {}
		self.recur(0, 0, nums)
		return sorted(list(self.result))


class Solution:

	def DistinctSum(self, l):
		n = len(l)
		r = [0]
		d = {}
		for i in l:
			l = []
			for j in r:
				if i + j not in d:
					d[i + j] = 1
					l.append(i + j)
			for k in l:
				r.append(k)
			if i not in d:
				r.append(i)
			d[i] = 1
		r.sort()
		return r


class Solution:

	def solve(self, i, nums, ans, dp, S=[]):
		if i == len(nums):
			ans.add(sum(S))
			return ans
		if dp[i] != False:
			return dp[i]
		dp[i] = self.solve(i + 1, nums, ans, dp, S)
		S.append(nums[i])
		dp[i] = self.solve(i + 1, nums, ans, dp, S)
		S.pop()

	def DistinctSum(self, arr):
		Sum = sum(arr)
		dp = [[False for i in range(Sum + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			dp[i][arr[i - 1]] = True
			for j in range(1, Sum + 1):
				if dp[i - 1][j] == True:
					dp[i][j] = True
					dp[i][j + arr[i - 1]] = True
		ans = []
		for j in range(Sum + 1):
			if dp[n][j] == True:
				ans.append(j)
		return ans


from collections import defaultdict

class Solution:

	def DistinctSum(self, nums):
		sums = {0}
		for x in nums:
			sums.update([s + x for s in sums])
		return sorted(sums)


class Solution:

	def DistinctSum(self, nums):
		d = {0: 1}
		s = [0]
		for i in range(len(nums)):
			for j in range(len(s)):
				if nums[i] + s[j] not in d:
					d[nums[i] + s[j]] = 1
					s.append(nums[i] + s[j])
		s.sort()
		return s


class Solution:

	def DistinctSum(self, nums):
		n = len(nums)
		s = sum(nums)
		dp = [[0 for i in range(0, s + 1)] for j in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = 1
		for i in range(1, n + 1):
			dp[i][nums[i - 1]] = 1
			for j in range(1, s + 1):
				if dp[i - 1][j] == 1:
					dp[i][j] = 1
					dp[i][j + nums[i - 1]] = 1
		ans = []
		for i in range(s + 1):
			if dp[n][i] == 1:
				ans.append(i)
		return ans


class Solution:

	def DistinctSum(self, nums):
		nums = nums
		foundnums = {0}
		for num in nums:
			befores = list(foundnums)
			for before in befores:
				foundnums.add(before + num)
		return sorted(foundnums)


class Solution:

	def DistinctSum(self, nums):
		ans = []
		dp = set()
		self.dfs(nums, 0, 0, ans, dp)
		ans = list(set(ans))
		ans.sort()
		return ans

	def dfs(self, nums, i, sum1, ans, dp):
		if i == len(nums):
			ans.append(sum1)
			return
		if (i, sum1) in dp:
			return
		dp.add((i, sum1))
		self.dfs(nums, i + 1, sum1, ans, dp)
		self.dfs(nums, i + 1, sum1 + nums[i], ans, dp)


class Solution:

	def DistinctSum(self, nums):
		if len(nums) == 0:
			return [0]
		c = nums[0]
		u = self.DistinctSum(nums[1:])
		return sorted(list(set(u + [a + c for a in u])))


class Solution:

	def DistinctSum(self, nums):
		nums.sort()
		seti = set([0])
		lis = [0]
		for i in nums:
			n = len(lis)
			for j in range(n):
				if i + lis[j] not in seti:
					lis.append(i + lis[j])
					seti.add(i + lis[j])
		lis.sort()
		return lis


class Solution:

	def solve(self, i, nums, tot, ans, dp):
		if i == len(nums):
			ans.add(tot)
			return
		if dp[i][tot] != -1:
			return
		dp[i][tot] = 1
		self.solve(i + 1, nums, tot, ans, dp)
		self.solve(i + 1, nums, tot + nums[i], ans, dp)

	def DistinctSum(self, nums):
		ans = set()
		sm = sum(nums)
		n = len(nums)
		dp = [[-1 for i in range(sm + 1)] for j in range(n + 1)]
		self.solve(0, nums, 0, ans, dp)
		s = list(ans)
		s.sort()
		return s


class Solution:

	def DistinctSum(self, nums):
		dic = {}
		dp = [[-1 for i in range(sum(nums) + 1)] for j in range(len(nums))]

		def f(i, summ):
			if i < 0:
				if summ not in dic:
					dic[summ] = 1
				return summ
			if dp[i][summ] != -1:
				return dp[i][summ]
			pick = f(i - 1, summ + nums[i])
			notpick = f(i - 1, summ)
			dp[i][summ] = [pick, notpick]
			return dp[i][summ]
		f(len(nums) - 1, 0)
		lst = []
		for key in dic:
			lst.append(key)
		return sorted(lst)


class Solution:

	def DistinctSum(self, nums):
		dsm = {0: 1}
		ln = len(nums)
		nums = list(nums)
		nums.sort()
		for i in range(ln):
			ne = nums[i]
			kys = list(dsm.keys()).copy()
			for j in kys:
				sm = ne + j
				if sm not in dsm.keys():
					dsm[sm] = 1
		rslt = list(dsm.keys())
		rslt.sort()
		return rslt


class Solution:

	def DistinctSum(self, nums):
		ans = {0}
		for i in nums:
			temp = set()
			for x in ans:
				temp.add(x + i)
			ans = ans.union(temp)
		return sorted(ans)


class Solution:

	def DistinctSum(self, nums):
		summ = sum(nums)
		dp = [0 for i in range(summ + 1)]
		dp[0] = 1
		n = len(nums)
		for i in range(1, n + 1):
			temp = [0 for k in range(summ + 1)]
			for j in range(summ + 1):
				nottake = dp[j]
				take = 0
				if nums[i - 1] <= j:
					take = dp[j - nums[i - 1]]
				temp[j] = take or nottake
			dp = temp.copy()
		res = []
		for i in range(summ + 1):
			if dp[i] == 1:
				res.append(i)
		return res


class Solution:

	def generate(self, lt, o):
		k = set()
		for i in lt:
			k.add(i)
			k.add(i + o)
		return list(k)

	def DistinctSum(self, nums):
		res = [0]
		for i in range(len(nums) - 1, -1, -1):
			res = self.generate(res, nums[i])
		return sorted(res)


class Solution:

	def DistinctSum(self, nums):
		n = len(nums)
		m = sum(nums) + 1
		dp = [[0 for _ in range(m)] for _ in range(n)]
		for j in range(m):
			if j == nums[0]:
				dp[0][j] = 1
		for i in range(n):
			dp[i][0] = 1
		for i in range(n):
			for j in range(m):
				if i == 0 or j == 0:
					continue
				elif nums[i] <= j:
					dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
				else:
					dp[i][j] = dp[i - 1][j]
		ans = []
		for j in range(m):
			present = False
			for i in range(n):
				if dp[i][j] == 1:
					present = True
			if present:
				ans.append(j)
		return ans


class Solution:

	def DistinctSum(self, nums):
		res = {0}
		for ans in nums:
			res.update([r + ans for r in res])
		return sorted(res)


class Solution:

	def DistinctSum(self, nums):
		total = sum(nums)
		dp = [True] + [False] * total
		for x in nums:
			for i in range(total - x, -1, -1):
				if dp[i]:
					dp[i + x] = True
		return [i for i in range(total + 1) if dp[i]]


class Solution:

	def DistinctSum(self, nums):
		uset = {0}
		for i in nums:
			temp = []
			for j in uset:
				temp.append(i + j)
			for j in temp:
				uset.add(j)
		ans = list(uset)
		ans.sort()
		return ans


class Solution:

	def DistinctSum(self, nums):
		ln = len(nums)
		sm = sum(nums)
		dp = [[False] * (sm + 1) for _ in range(ln + 1)]
		for i in range(ln + 1):
			dp[i][0] = True
			if i > 0:
				dp[i][nums[i - 1]] = True
		for i in range(1, ln + 1):
			for j in range(sm + 1):
				dp[i][j] = dp[i - 1][j]
				if j - nums[i - 1] >= 0:
					dp[i][j] = dp[i][j] or dp[i - 1][j - nums[i - 1]]
		res = set()
		for i in range(sm + 1):
			if dp[-1][i]:
				res.add(i)
		return sorted(list(res))


class Solution:

	def DistinctSum(self, nums):
		res = set()
		res.add(0)
		for num in nums:
			lst = []
			for r in res:
				lst.append(r + num)
			res.update(lst)
		return sorted(list(res))


class Solution:

	def DistinctSum(self, nums):
		totalsum = sum(nums)
		dp = [[False for i in range(totalsum + 1)] for j in range(len(nums) + 1)]
		for i in range(len(nums) + 1):
			dp[i][0] = True
		for i in range(1, len(nums) + 1):
			dp[i][nums[i - 1]] = True
			for j in range(1, totalsum + 1):
				if dp[i - 1][j]:
					dp[i][j] = True
					dp[i][j + nums[i - 1]] = True
		res = []
		for i in range(totalsum + 1):
			if dp[len(nums)][i]:
				res.append(i)
		return res


class Solution:

	def DistinctSum(self, nums):
		res = set()
		res.add(0)
		a = [0]
		for i in nums:
			ls = []
			for r in res:
				ls.append(r + i)
			res.update(ls)
		return sorted(list(res))


class Solution:

	def DistinctSum(self, nums):
		s = sum(nums)
		t = len(nums)
		dp = [0 for i in range(s + 1)]
		dp[0] = 1
		for i in range(1, t + 1):
			temp = [0 for i in range(s + 1)]
			temp[0] = 1
			for j in range(1, s + 1):
				if j < nums[i - 1]:
					temp[j] = dp[j]
				elif dp[j - nums[i - 1]]:
					temp[j] = 1
				else:
					temp[j] = dp[j]
			dp = temp[:]
		ans = []
		for i in range(s + 1):
			if dp[i]:
				ans.append(i)
		return ans


class Solution:

	def DistinctSum(self, nums):
		arr = {0}
		for i in nums:
			temp = {0}
			for j in arr:
				if i + j not in arr and i + j not in temp:
					temp.add(i + j)
			arr.update(temp)
		return sorted(list(arr))


class Solution:

	def DistinctSum_old(self, nums):
		ans = [0]
		for n in nums:
			ans.append(n)
		for i in range(len(nums) - 1):
			val = nums[i] + nums[i + 1]
			if val not in ans:
				ans.append(val)
			val = nums[i]
			for j in range(i - 1, -1 - 1):
				val += nums[j]
				if val not in ans:
					ans.append(val)
		ans.sort()
		return ans

	def DistinctSum(self, arr):
		ans = []
		Sum = sum(arr)
		n = len(arr)
		dp = [[False for i in range(Sum + 1)] for i in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			dp[i][arr[i - 1]] = True
			for j in range(1, Sum + 1):
				if dp[i - 1][j] == True:
					dp[i][j] = True
					dp[i][j + arr[i - 1]] = True
		for j in range(Sum + 1):
			if dp[n][j] == True:
				ans.append(j)
		return ans


class Solution:

	def DistinctSum(self, nums):
		(n, total) = (len(nums), sum(nums))
		memo = [[True] + [False] * total for _ in range(n)]
		nums = sorted(nums)
		memo[0][nums[0]] = True
		for (i, v) in enumerate(nums[1:], 1):
			for tot in range(1, total + 1):
				if tot < v:
					memo[i][tot] = memo[i - 1][tot]
					continue
				memo[i][tot] |= memo[i - 1][tot] or memo[i - 1][tot - v]
		return [i for i in range(total + 1) if memo[n - 1][i]]


class Solution:

	def DistinctSum(self, nums):
		ans = []
		s1 = sum(nums)
		dp = []
		for i in range(s1 + 1):
			c = []
			for j in range(len(nums)):
				c.append(-1)
			dp.append(c)

		def sum1(i, s):
			if i >= len(nums):
				ans.append(s)
				return
			if dp[s][i] != -1:
				return dp[s][i]
			sum1(i + 1, s + nums[i])
			sum1(i + 1, s)
			dp[s][i] = s
			return dp[s][i]
		sum1(0, 0)
		a = set(ans)
		a = list(a)
		a.sort()
		return a


class Solution:

	def DistinctSum(self, nums):
		nums.sort()
		sett = set([0])
		ls = [0]
		for i in nums:
			n = len(ls)
			for j in range(n):
				if i + ls[j] not in sett:
					ls.append(i + ls[j])
					sett.add(i + ls[j])
		ls.sort()
		return ls


class Solution:

	def DistinctSum(self, nums):
		n = len(nums)
		s = sum(nums)
		dp = [[False] * (s + 1) for _ in range(n + 1)]
		for i in range(n + 1):
			dp[i][0] = True
		for i in range(1, n + 1):
			for j in range(1, s + 1):
				if nums[i - 1] <= j:
					dp[i][j] = dp[i - 1][j - nums[i - 1]] or dp[i - 1][j]
				else:
					dp[i][j] = dp[i - 1][j]
		a = []
		for i in range(s + 1):
			if dp[n][i]:
				a.append(i)
		return a


class Solution:

	def DistinctSum(self, nums):
		n = len(nums)
		s0 = sum(nums)
		dp = [[False] * (s0 + 1) for _ in range(n + 1)]
		for j in range(n + 1):
			dp[j][0] = True
		for j in range(n):
			for s in range(1, s0 + 1):
				dp[j + 1][s] = dp[j + 1][s] or dp[j][s]
				if s - nums[j] >= 0:
					dp[j + 1][s] = dp[j + 1][s] or dp[j][s - nums[j]]
		return [s for s in range(s0 + 1) if dp[n][s]]


class Solution:

	def DistinctSum(self, nums):
		nums.sort()
		res = set([0])
		l = [0]
		for i in nums:
			n = len(l)
			for j in range(n):
				if i + l[j] not in res:
					l.append(i + l[j])
					res.add(i + l[j])
		l.sort()
		return l