Partition to K Equal Sum Subsets


@jazzikpeng said in Partition to K Equal Sum Subsets:
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?



@quincyhehe Because we stop when
groups[i]
is zero, the firstk
times the solution runs, there is at mosti
choices fornums[i]
wheni <= k
.@LeonCheng Thanks, appreciate it.

@thakursc1 said in Partition to K Equal Sum Subsets:
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?
Do you mean like the case I had already posted right above your question?
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((nk + 1)^k) ?

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

@siyao Because even though Nk+1 is the most items you can put in a group, you still have to put all N items, not just Nk+1 of them.

@uduchi.2ndgmail.com The topdown version does not search the entire tree when it finds a solution quickly, and we find a solution quickly in greedy order on average.