# Divide a set into subset with some constraints

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

## Problem:

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.

### Examples:


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)

'''
@lru_cache(maxsize=None)
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?

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