给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。
数组的 第 k 大和 定义为:可以获得的第 k 个 最大 子序列和(子序列和允许出现重复)
返回数组的 第 k 大和 。
子序列是一个可以由其他数组删除某些或不删除元素派生而来的数组,且派生过程不改变剩余元素的顺序。
提交的时候一直显示超过内存限制,有什么优化的方法吗?
class Solution():
def kSum(self, nums, k):
from itertools import combinations
kind = {}
for i in range(1,len(nums)+1):
for a in list(combinations(nums, i)):
kind[sum(a)] = kind.get(sum(a),0) + 1
kind[0] = kind.get(0,0) +1
for i in sorted(kind.items(),key=lambda x:x[0],reverse=True):
if k <= i[1]:
return i[0]
k -= i[1]