Desafío
Escriba una función que desde una matriz de entrada arbitraria seleccionará todas las combinaciones de números cuya suma sea 10.A primera vista, la tarea es simple, todo lo que necesita hacer es escribir una recursión y ordenar todos los valores.
O puede usar un incremento binario, pero para iterar sobre todos los valores para un vector de números de longitud N, se necesitan 2 ^ n iteraciones.
Primero, elegimos un caso especial, supongamos que la matriz consiste en números> 0. Luego, en base a este ejemplo, implementaremos todos los casos.PASO 1
a) Considere uno de los casos especiales: la suma de todos los elementos de la matriz <10.
La lógica es simple, suma (V) <10, luego suma (V) -V [i] <suma, es decir, si la suma de las combinaciones siempre será menor que 10.
b) Si suma (V) = 10, entonces la suma suma (V) -V [i] <suma. El resultado será solo un
v .
PASO 2
Eliminamos todo lo innecesario del vector.
Como ejemplo, tome la matriz [13, 10, 20, 13, 13, 18, 2, 9, 5, 8, 8, 9, 2, 1, 8, 16, 4, 15, 2, 2, 2, 1, 5 , 5, 5].
Muestra de inmediato que no tiene sentido buscar combinaciones si el valor es> 10, pero todo se aclarará de inmediato. si lo clasificamos:
[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 15, 16, 18, 20 ]
En esta etapa, ya podemos saber con certeza que necesitamos eliminar todos los elementos mayores de 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]
Pero, de hecho, todo es un poco más interesante. necesitamos limitar el vector al valor para que V [0] + V [i] <= 10; donde tiendo a N; Pero si V [i] = 10, entonces agregamos 10 al resultado
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]
PASO 3
Hay elementos duplicados en una matriz ya filtrada. Si descomponemos el vector en sub-vectores y calculamos su suma, obtenemos algo como esto
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[5, 5, 5, 5] => 20
[8, 8, 8] => 24
[9,9] => 18
La esencia de mis pensamientos es tal que no tiene sentido considerar combinaciones de números repetidos si su número * valor> 10. Es decir, cortamos los vectores hasta que su suma sea menor que 10, y agreguemos los que son 10 al resultado:
[1,1] => [1,1]
[2, 2, 2, 2, 2] => [2, 2, 2, 2]
[4] => [4]
[5, 5, 5, 5] => [5]
[8, 8, 8] => [8]
[9,9] => [9]
Como resultado del tercer paso, nuestro vector será el siguiente
[1, 1, 2, 2, 2, 4, 5, 8, 9]
Como puede ver, el tamaño del vector ha disminuido de 25 a 9, es mucho más pequeño (recuerde el número de iteraciones);
Con números negativos
Esto es un poco más complicado. asumiremos que hemos implementado la función de encontrar combinaciones para un vector ordenado positivo basado en las restricciones anteriores.
comb (arr, sum), donde sum es la cantidad requerida, arr es un vector ordenado de números positivos
Por ejemplo, tome el vector:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12 , -10, 9]
1. Romper el vectorA = solo valores positivos
B = solo valores negativos
Y también ver si tenemos valores = 0
2. OrdenarOrdenar los vectores (positivo ascendente, negativo descendente)
Verifique el caso especial para números positivos (PASO 1)
3. Verificación de positivoVerificar valores positivos
peine (B, 10)3. Comprobar si hay negativocrear combinaciones de todos los números negativos, pero con la restricción:
(suma de elementos módulo) <(suma de todos los positivos) + 10
encontramos combinaciones para las NUEVAS sumas de referencia (la suma de los elementos módulo + 10)
4. Igualdad 0Si el vector fuente tiene un valor de 0, entonces agregamos todas las combinaciones + 0 al resultado;
Como resultado de tales limitaciones, en promedio, cuando se prueban valores con una matriz de 28 y 1000 pruebas de largo, la ganancia de tiempo es casi 42%
Tenga cuidado de no parecer nervioso. El autor no es responsable del sufrimiento moral.function combine(arr, etalon = 10) {