Skip to content

Latest commit

 

History

History
106 lines (60 loc) · 3.8 KB

3082-find-the-sum-of-the-power-of-all-subsequences.adoc

File metadata and controls

106 lines (60 loc) · 3.8 KB

3082. Find the Sum of the Power of All Subsequences

{leetcode}/problems/find-the-sum-of-the-power-of-all-subsequences/[LeetCode - 3082. Find the Sum of the Power of All Subsequences ^]

You are given an integer array nums of length n and a positive integer k.

The power of an array of integers is defined as the number of <span data-keyword="subsequence-array">subsequences with their sum equal to k.

Return the sum of power of all subsequences of `nums`.

Since the answer may be very large, return it modulo 109 + 7.

Example 1:

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;"> *Input: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> nums = [1,2,3], k = 3

*Output: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 6

Explanation:

There are 5 subsequences of nums with non-zero power:

  • The subsequence 1,2,3] has 2 subsequences with sum == 3: 3] and 1,2,3].

  • The subsequence 1,2,3] has 1 subsequence with sum == 3: 3].

  • The subsequence 2,3] has 1 subsequence with sum == 3: 3].

  • The subsequence 1,2,3] has 1 subsequence with sum == 3: 1,2,3].

  • The subsequence 3] has 1 subsequence with sum == 3: 3].

Hence the answer is 2 + 1 + 1 + 1 + 1 = 6.

Example 2:

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;"> *Input: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> nums = [2,3,3], k = 5

*Output: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 4

Explanation:

There are 3 subsequences of nums with non-zero power:

  • The subsequence 2,3,3] has 2 subsequences with sum == 5: 2,3,3] and 2,3,3].

  • The subsequence 2,3,3] has 1 subsequence with sum == 5: 2,3,3].

  • The subsequence 2,3,3] has 1 subsequence with sum == 5: 2,3,3].

Hence the answer is 2 + 1 + 1 = 4.

Example 3:

<div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;"> *Input: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> nums = [1,2,3], k = 7

*Output: * <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 0

*Explanation: *There exists no subsequence with sum 7. Hence all subsequences of nums have power = 0.

Constraints:

  • 1 ⇐ n ⇐ 100

  • 1 ⇐ nums[i] ⇐ 104

  • 1 ⇐ k ⇐ 100

思路分析

一刷
link:{sourcedir}/_3082_FindTheSumOfThePowerOfAllSubsequences.java[role=include]

参考资料