#3082

Find the Sum of the Power of All Subsequences

hard · 38.1% accepted · 168 likes · top 17%

array · dynamic programming

⊣ practice⊣ open on leetcode ↗

Description

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 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.

Solution