Derivar un MultiSet de un Array dado tal que la suma sea > P y la eliminación de cualquier elemento haga que la suma < P

Dada una array arr[] de N elementos, la tarea es derivar un MultiSet que tenga los números de la array dada en posibles repeticiones, de modo que la suma del MultiSet sea estrictamente mayor que el número P dado y si se elimina alguno de los elementos , entonces la suma se vuelve estrictamente menor que P . Imprime el número de veces que el elemento correspondiente de la array dada se deriva al MultiSet. Imprima -1 si no se puede derivar tal MultiSet.

Ejemplos:

Entrada: arr[] = [1, 5], P = 4
Salida: [0, 1] 
Explicación: 
Aquí, si el número 1 se toma 0 veces y el 5 se toma 1 vez, el MultiSet se convierte en: [5]
Por lo tanto, suma = 5 (>P) y quitando 5 hace suma = 0 (<P). Por lo tanto, el MultiSet requerido es [5].
Por lo tanto, la salida es [0, 1] como el número de veces que se toman 1 y 5 respectivamente.

Entrada: arr[] = [1, 5], P = 10
Salida: -1
Explicación: 
si tomamos un conjunto múltiple como [1, 5, 5], la suma será > P, pero quitar 1 no hará que la suma < P. Por lo tanto, no se puede derivar tal MultiSet en este caso.

Enfoque:
La principal observación del problema anterior es que, si P es indivisible por cualquiera de los elementos del arreglo arr[], entonces tomamos todos los múltiplos de ese elemento de modo que la suma sea estrictamente mayor que p. Pero si no existe tal elemento en la array y el conjunto múltiple es posible, ordenamos la array en orden descendente y tomamos múltiplos de cada elemento uno menos que P % arr[i] y seguimos actualizando la P. El conjunto múltiple no es posible si cada vez que la P actualizada es divisible por arr[i+1] hasta N.
 
A continuación se muestra la implementación del enfoque anterior:

# Python implementation to Derive a
# MultiSet from given Array such that
# sum is > P and removing any
# element makes sum < P
  
# Function to derive the multiset
def Multiset (n, p, arr):
      
    c = 0
      
    for j in arr:
          
        # Check if p is indivisible
        # by any element in arr
        if (p % j != 0):
            c = j
            break
              
    # Check if there is no element in
    # arr which cannot divide p    
    if (c == 0):
          
        d = sorted(arr)
          
        # Sort arr in descending order
        d = d[::-1]         
        coun = 0
        pri = [0] * n
          
        # Assigning multiples of each element
        while (coun != n and p % d[coun] == 0): 
            
            b = arr.index(d[coun])
            pri[b] = ((p//d[coun]) - 1)
            p = p - (d[coun]*((p//d[coun]) - 1))
            coun += 1
          
        # Check if there is no case
        # of getting sum > p
        if (coun == n):
            return ("NO")
              
        elif (p % d[coun] != 0):
            y = (p//d[coun]) + 1
            k = arr.index(d[coun])
              
            pri[k] = y
            s = ""
              
            # Multi set
            for j in pri:                     
                s = s + str(j) + " "
            return (s)
          
              
    else:
        k = p//c
        b = c * (k + 1)
        m = [0] * n
        q = arr.index(c)
        m[q] = b//c
        s = ""
        for j in m:
            s = s + str(j) + " "
        return (s)
  
# Driver code
N, P = 2, 4
arr = [1, 5]
print (Multiset(N, P, arr))

0 1 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)