求助:关于和前缀和有关的一道题

题面：

一个长度为N的数组A，从A中选出若干个数，使得这些数的和是N的倍数。(2 <= N <= 50000,0 < A[i] <= 10^9)

输出：如果没有符合条件的组合，输出No Solution。 第1行：1个数S表示你所选择的数的数量。 第2 - S + 1行：每行1个数，对应你所选择的数。

我想了大概半个小时，只想出记忆化搜索这种不太可靠的法子。然后我看了题解,看是看懂了，但是我实在不知道是如何想到前缀和+抽屉的。想请问各位这道题想到前缀和解法的思维难度大概是多少？