Python 3 Solution (Dynamic Programing) Time Complexity: O(n*n*total_sum)


#1

res = []
memoize = {}
def dp(A,index,find_sum,length):

if find_sum == 0 and length == 0:
    return True
    
if find_sum<0 or length<0 or index>=len(A):
    return False
    
string_key = str(index)+"-"+str(find_sum)+"-"+str(length)

if memoize.get(string_key)!=None:
    return memoize[string_key]
    
res.append(A[index])

if dp(A,index+1,find_sum-A[index],length-1):
    memoize[string_key] = True
    return True
    
res.pop()

if dp(A,index+1,find_sum,length):
    memoize[string_key] = True
    return True
    
memoize[string_key] = False
return False

class Solution:
# @param A : list of integers
# @return a list of list of integers
def avgset(self, A):
global res
global memoize
memoize = {}
A.sort()
find_sum = None
sum1 = sum(A)
val = False
for i in range(1,len(A)-1):
res = []
if (sum1i)%len(A)==0:
find_sum = (sum1
i)//len(A)
length = i
val = dp(A,0,find_sum,length)
if val:break
if val != True:
return []
else:
mapper = {}
minus = []
for i in res:
if mapper.get(i):
mapper[i]+=1
else:
mapper[i] = 1
for i in A:
if mapper.get(i) and mapper.get(i)!=0:
mapper[i]-=1
else:
minus.append(i)
if len(res)==len(minus):
for i in range(len(res)):
if res[i]>minus[i]:
res,minus = minus,res
break
elif res[i]==minus[i]:
pass
else:
break
elif len(res)>len(minus):
res,minus = minus,res
return [res,minus]