Dada una array A[] que consta de N enteros, la tarea es dividir la array A[] en subconjuntos que tengan la misma suma y una longitud igual a los elementos de la array B[] .
Ejemplos:
Entrada: A[] = {17, 13, 21, 20, 50, 29}, B[] = {2, 3, 1}
Salida:
21 29
17 13 20
50Entrada: A[] = { 1, 2, 3, 4, 5, 6}, B[] = { 2, 2, 2}
Salida:
1 6
2 5
3 4
Enfoque: siga los pasos a continuación para resolver el problema:
- Dado que el recuento de subconjuntos ya está dado, calcule la suma de cada subconjunto.
- Recorra cada elemento de la array B[], encuentre cada combinación posible de longitud B[i] y verifique si la suma de la combinación es igual a la suma deseada o no.
- Repita los pasos anteriores para cada elemento de array B[i] e imprima la respuesta final
A continuación se muestra la implementación del enfoque anterior:
Python
# Python Program to implement # the above approach from itertools import combinations # Function to split elements of first # array into subsets of size given as # elements in the second array def main(A, B): # Required sum of subsets req_sum = sum(A) // len(B) # Stores the subsets final = [] # Iterate the array B[] for i in B: # Generate all possible # combination of length B[i] temp = list(combinations(A, i)) # Iterate over all the combinations for j in temp: # If the sum is equal to the # required sum of subsets if(sum(j) == req_sum): # Store the subset temp = list(j) final.append(temp) for k in temp: # Removing the subset # from the array A.remove(k) break # Printing the final result print(final) # Driver Code if __name__ == '__main__': # Value of array A and B A = [1, 2, 3, 4, 5, 6] B = [2, 2, 2] # Function call main(A, B)
Producción:
[[1, 6], [2, 5], [3, 4]]
Complejidad de tiempo: O(N 3 )
Espacio auxiliar: O(2 maxm ), donde maxm es el elemento máximo en el arreglo B[]
Publicación traducida automáticamente
Artículo escrito por jatindscl015 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA