3098.求出所有子序列的能量和

链接：3098.求出所有子序列的能量和
难度：Hard
标签：数组、动态规划、排序
简介：请你返回 nums 中长度 等于 k 的 所有 子序列的 能量和 。

题解 1 - python

• 编辑时间：2024-07-23
• 执行用时：3583ms
• 内存消耗：759.11MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def sumOfPowers(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        @cache
        def dfs(idx: int, k: int, prev_idx: int, cur_min: int) -> int:
            if k == 0: return cur_min
            if idx == n: return 0
            next_min = cur_min if prev_idx == -1 else min(cur_min, nums[idx] - nums[prev_idx])
            return dfs(idx + 1, k, prev_idx, cur_min) + dfs(idx + 1, k - 1, idx, next_min)
        return dfs(0, k, -1, inf) % (10 ** 9 + 7)