Leetcode Problem 805. Split Array With Same Average

805. Split Array With Same Average

Leetcode Solutions

Dynamic Programming with Bitmasking

  1. Calculate the total sum of the array and store it as totalSum.
  2. Initialize a bitmask dp with size totalSum + 1, where each element is an integer representing possible subset sizes for that sum.
  3. Set the first element of the array in the bitmask dp.
  4. Iterate through the array, updating the bitmask for each element.
  5. For each element A[i], update dp[s+A[i]] by OR-ing it with dp[s] shifted left by 1 bit.
  6. After updating the bitmask for all elements, iterate through all possible subset sizes from 1 to n-1.
  7. For each size len, check if the sum totalSum * len / n is achievable by checking the len-th bit in dp[totalSum * len / n].
  8. If such a subset size and sum exist, return true; otherwise, return false after the loop.
UML Thumbnail

Early Pruning and Knapsack DP

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...