This is documentation for my solution to 466C - Number of Ways. Credit for Coding Hangover for the algorithm. This post will detail the approach here, as well as provide an example.

Problem Statement

Given an array arr, we are to compute the number of ways we can partition arr into chunks where each chunk is contiguous. Further, the sum of the elements in each chunk must be the same.

Naive Approach

My first approach to this problem was to pre-compute an array A which is a running sum of arr. Concretely, A[i] = sum(a[:i]) inclusive.