All Subset Sums
Programming Interview
Hard
17 views
Problem Description
Consider {x}. Use recursion function dfs(i,cur) to generate all subset sums. Output sums sorted.
Input Format
First line n. Second line n integers.
Output Format
All sums sorted space-separated.
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
res=[]
def dfs(i,cur):
if i==n:
res.append(cur)
return
dfs(i+1,cur)
dfs(i+1,cur+a[i])
dfs(0,0)
res.sort()
sys.stdout.write(' '.join(map(str,res)))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!