Skip to content

3082. Find the Sum of the Power of All Subsequences 👍

Approach 1: Top-down

  • Time: $O(nk)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  int sumOfPower(vector<int>& nums, int k) {
    vector<vector<int>> mem(nums.size(), vector<int>(k + 1, -1));
    return sumOfPower(nums, 0, k, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of subsequences in nums[i..n) that sums to j.
  int sumOfPower(const vector<int>& nums, int i, int j,
                 vector<vector<int>>& mem) {
    if (j == 0)
      // For each of the remaining number, we can either pick it or skip it.
      return modPow(2, nums.size() - i);
    if (i == nums.size() || j < 0)
      return 0;
    if (mem[i][j] != -1)
      return mem[i][j];
    // 1. Include nums[i] in the subsequence and pick it.
    // 2. Include nums[i] in the subsequence and skip it.
    // 3. Exclude nums[i] in the subsequence.
    return mem[i][j] = (sumOfPower(nums, i + 1, j - nums[i], mem) +
                        2L * sumOfPower(nums, i + 1, j, mem)) %
                       kMod;
  }

  long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public int sumOfPower(int[] nums, int k) {
    Integer[][] mem = new Integer[nums.length][k + 1];
    return sumOfPower(nums, 0, k, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of subsequences in nums[i..n) that sums to j.
  private int sumOfPower(int[] nums, int i, int j, Integer[][] mem) {
    if (j == 0)
      // For each of the remaining number, we can either pick it or skip it.
      return (int) modPow(2, nums.length - i);
    if (i == nums.length || j < 0)
      return 0;
    if (mem[i][j] != null)
      return mem[i][j];
    // 1. Include nums[i] in the subsequence and pick it.
    // 2. Include nums[i] in the subsequence and skip it.
    // 3. Exclude nums[i] in the subsequence.
    return mem[i][j] = (int) ((sumOfPower(nums, i + 1, j - nums[i], mem) + //
                               2L * sumOfPower(nums, i + 1, j, mem)) %
                              kMod);
  }

  private long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def sumOfPower(self, nums: list[int], k: int) -> int:
    kMod = 1_000_000_007

    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """Returns the number of subsequences in nums[i..n) that sums to j."""
      if j == 0:
        # For each of the remaining number, we can either pick it or skip it.
        return pow(2, len(nums) - i, kMod)
      if i == len(nums) or j < 0:
        return 0
        # 1. Include nums[i] in the subsequence and pick it.
        # 2. Include nums[i] in the subsequence and skip it.
        # 3. Exclude nums[i] in the subsequence.
      return (dp(i + 1, j - nums[i]) + 2 * dp(i + 1, j)) % kMod

    return dp(0, k)

Approach 2: Bottom-up 2D DP

  • Time: $O(nk)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int sumOfPower(vector<int>& nums, int k) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    // dp[i][j] := the number of subsequences in nums[0..i) that sums to k
    vector<vector<int>> dp(n + 1, vector<int>(k + 1));
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
      const int num = nums[i - 1];
      for (int j = 0; j <= k; ++j)
        if (j < num)
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          dp[i][j] = (dp[i - 1][j] * 2L) % kMod;
        else
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          // 3. Include nums[i] in the subsequence and pick it.
          dp[i][j] = (dp[i - 1][j] * 2L + dp[i - 1][j - num]) % kMod;
    }

    return dp[n][k];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int sumOfPower(int[] nums, int k) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    // dp[i][j] := the number of subsequences in nums[0..i) that sums to k
    int[][] dp = new int[n + 1][k + 1];
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
      final int num = nums[i - 1];
      for (int j = 0; j <= k; ++j)
        if (j < num)
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          dp[i][j] = (int) ((dp[i - 1][j] * 2L) % kMod);
        else
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          // 3. Include nums[i] in the subsequence and pick it.
          dp[i][j] = (int) ((dp[i - 1][j] * 2L + dp[i - 1][j - num]) % kMod);
    }

    return dp[n][k];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def sumOfPower(self, nums: list[int], k: int) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    # dp[i][j] := the number of subsequences in nums[0..i) that sums to k
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
      num = nums[i - 1]
      for j in range(k + 1):
        if j < num:
          # 1. Exclude nums[i] in the subsequence.
          # 2. Include nums[i] in the subsequence and skip it.
          dp[i][j] = (dp[i - 1][j] * 2) % kMod
        else:
          # 1. Exclude nums[i] in the subsequence.
          # 2. Include nums[i] in the subsequence and skip it.
          # 3. Include nums[i] in the subsequence and pick it.
          dp[i][j] = (dp[i - 1][j] * 2 + dp[i - 1][j - num]) % kMod

    return dp[n][k]

Approach 3: Bottom-up 1D DP

  • Time: $O(nk)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int sumOfPower(vector<int>& nums, int k) {
    constexpr int kMod = 1'000'000'007;
    // dp[i] := the number of subsequences in nums so far that sums to k
    vector<int> dp(k + 1);
    dp[0] = 1;

    for (const int num : nums)
      for (int i = k; i >= 0; --i)
        if (i < num)
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          dp[i] = (dp[i] * 2L) % kMod;
        else
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          // 3. Include nums[i] in the subsequence and pick it.
          dp[i] = (dp[i] * 2L + dp[i - num]) % kMod;

    return dp[k];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int sumOfPower(int[] nums, int k) {
    final int kMod = 1_000_000_007;
    // dp[i] := the number of subsequences in nums so far that sums to k
    int[] dp = new int[k + 1];
    dp[0] = 1;

    for (final int num : nums)
      for (int i = k; i >= 0; --i)
        if (i < num)
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          dp[i] = (int) ((dp[i] * 2L) % kMod);
        else
          // 1. Exclude nums[i] in the subsequence.
          // 2. Include nums[i] in the subsequence and skip it.
          // 3. Include nums[i] in the subsequence and pick it.
          dp[i] = (int) ((dp[i] * 2L + dp[i - num]) % kMod);

    return dp[k];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def sumOfPower(self, nums: list[int], k: int) -> int:
    kMod = 1_000_000_007
    # dp[i] := the number of subsequences in nums so far that sums to k
    dp = [1] + [0] * k

    for num in nums:
      for i in range(k, -1, -1):
        if i < num:
          dp[i] = (dp[i] * 2) % kMod
        else:
          dp[i] = (dp[i] * 2 + dp[i - num]) % kMod

    return dp[k]