I was wondering if anyone knows how to solve the following problem. I have tried on-and-off for about a week now, but I cannot figure it out:

Given an array A of N(1 <= N <= 100000) positive integers. You have to find out for every k(1 <= k <= n), if it is possible to partition an array into k equal continuous subsequence sum.

For example: if A = [3, 2, 2, 1], the answer will be: 1100.

Note: For the first example: 1)For k = 1, we can partition an array as follows: [3, 2, 2, 1]. 2)For k = 2, we can partition an array as follows: [3, 1] and [2, 2]. 3)For k = 3 and 4, we can't partition an array into equal continuous subsequence sum. The first and last elements is also a continuous subsequence, because we are talking about a circle array.

I have tried DP, but it is also TLE. My algorithm works in O(n^2). Does anyone know how I can solve this?