Note - I am not sure whether this question belongs to stackoverflow or CSE stackexchange or here


Given a list Lconsisting of not necessarily unique non-negative integers, find the minimum number of subset with maximum sum k(given) in which it can be divided such that: each subset shouldn't contain consecutive elements from the list*.

(*): I can see an obvious ambiguity:
Q: If there is 3 4, is the restriction is on all 3 or just the adjacent three?

A: Just on adjacent 3.


1. L = [2, 1, 1, 2], k = 2 => 4 

Explanation: First set can take 0th index element
             second set can take 1st index element and similarly third and fourth can take 2nd and 3rd index element respectively

Here, you can see that k is working as a bottleneck

More examples:

L = [2, 4, 1, 0] k = 8 => 2

L = [3, 2, 3, 0, 0] k = 5 => 3

This seems to have some features of dynamic programming problems, so I went for dynamic programming and wrote the following recursive code:

from functools import lru_cache
def min_count(L, k):
    index - stores the current state's index
    sets - this stores information of already stored sets:
            It is tuple of tuple, 
                In each tuple:
                    First element - index of last stored element
                    Second element - stores the sum of current set
    k - It is limit|capacity of each subset(same as the one given in arugment)

    def recurse(index, sets, k):
        #If control reaches to the end of the list
        if index == len(L):
            return len(sets)

        #In case the current indexes is zero
        if L[index] == 0:

            #If this is the last index, then
            if index + 1 == len(L):
                return len(sets)
            return recurse(index + 1, sets, k)


        The job of this for loop is iterate all of the stored sets:
            And if that's capable of storing further, then add current index
            to it, and recurse
        m = 1e10
        for i, j in sets:
            if i - index < -1 and j + L[index] <= k:
                if index + 1 == len(sets):
                    return len(sets)
                m = min(m, recurse(index + 1,tuple(_ if _ != (i, j) else (index, j + L[index]) for _ in sets) , k))

        m = min(m, recurse(index + 1, sets + ((index, L[index]), ), k))
        return m

    return recurse(0, (), k)

The problem is that this code works, but is very slow(the expected time complexity must be lower than O(n^2)).

How can I make it fast?

  • \$\begingroup\$ when would more than two subsets be required? Taking every other element should be non consecutive \$\endgroup\$ Commented Jan 7, 2021 at 16:55
  • \$\begingroup\$ Example: L = [2, 2, 2, 2, 2] with k = 2 \$\endgroup\$
    – xrfxlp
    Commented Jan 7, 2021 at 17:04


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.