# Partition to K Equal Sum Subsets

• The first solution gets Time Limit Exceeded for example for the single case `nums = [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]`, `k = 5`.

• Can anyone give me a test case which passes the first filter in the approach 1 and then fails when we actually search for a number?

• I used a permutation, but TLE.

• This is a bad problem. Cause I can get an accepted with just a few line of tricks. In pretty much O(1) runtime.

• Sorry, I mean O(N).

• ``````int sum = Arrays.stream(nums).sum();
``````

The above line looks neat but for the small size array, your code doesn't benefit from it. If use a simple loop instead, the average run time will be reduced to ~70ms from ~150ms

• This is a bad problem. Cause I can get an accepted with just a few line of tricks.

Where can I see that? Looks like you forgot to post it?

• This post is deleted!

• @cannot_stop_eatingT-T Read the second note.

• @ManuelP thanks for pointing it out. Why didn't I see that!

• Why is the time complexity for the first solution O(k! K ^(n - k)), can you please give more detail? Where does k! come from?

• Awice, you are really awesome, I figured out the backtracking solution, but I never know we could do it in dynamic programming way. I have learned a lot from your article.

• @quincyhehe Because we stop when `groups[i]` is zero, the first `k` times the solution runs, there is at most `i` choices for `nums[i]` when `i <= k`.

@LeonCheng Thanks, appreciate it.

• Can anyone give me a test case which passes the first filter in the approach 1 and then fails when we actually search for a number?

Not sure what you mean with "search for a number"...

• @awice I still did not get the time complexity of 1st solution. Could you explain more? To me, In every recursion, we at most try k groups, which means the search tree has k branches at most. And the depth of the search tree is the max number of elements we can put in a group, which is N - k + 1. So why the time complexity is not O((n-k + 1)^k) ?

• @awice Correction... So why the time complexity is not O(k^(n-k+1)) or O(k^(n-k))? (where is the k! ?)

• @si-yao Because even though N-k+1 is the most items you can put in a group, you still have to put all N items, not just N-k+1 of them.

• I got 1669 ms bottom-version of Approach 2 but the top-down version got 386ms. Can anyone help me understand why the bottom-up version is much worse in this situation? In a contest, usually which approach should be easier to work on?

• @uduchi.2nd-gmail.com The top-down version does not search the entire tree when it finds a solution quickly, and we find a solution quickly in greedy order on average.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.