Desafio
Escreva uma função que, a partir de uma matriz de entrada arbitrária, selecione todas as combinações de números cuja soma é 10.À primeira vista, a tarefa é simples, tudo o que você precisa fazer é escrever uma recursão e classificar todos os valores.
Ou você pode usar um incremento binário, mas para iterar sobre todos os valores de um vetor de número de comprimento N, são necessárias 2 ^ n iterações.
Primeiro, escolhemos um caso especial, suponha que a matriz seja composta por números> 0. Posteriormente, com base neste exemplo, implementaremos todos os casos.PASSO 1
a) Considere um dos casos especiais - a soma de todos os elementos da matriz <10.
A lógica é simples, soma (V) <10, então soma (V) -V [i] <soma, isto é, se a soma das combinações sempre for menor que 10.
b) Se soma (V) = 10, então a soma soma (V) -V [i] <soma. O resultado será apenas um
v .
PASSO 2
Nós removemos todos os desnecessários do vetor
Como exemplo, considere a 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].
Isso mostra imediatamente que não faz sentido procurar combinações se o valor for> 10, mas tudo ficará imediatamente claro. se classificarmos:
[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 13, 15, 16, 18, 20 ]
Nesse estágio, já podemos ter certeza de que precisamos excluir todos os elementos maiores que 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]
Mas, de fato, tudo é um pouco mais interessante. precisamos limitar o vetor ao valor para que V [0] + V [i] <= 10; onde eu tendem a N; Mas se V [i] = 10, então adicionamos 10 ao resultado
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]
PASSO 3
Existem elementos duplicados em uma matriz já filtrada. Se decompormos o vetor em sub-vetores e calcularmos sua soma, obteremos algo como isto
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[5, 5, 5, 5] => 20
[8, 8, 8] => 24
[9,9] => 18
A essência dos meus pensamentos é tal que não faz sentido considerar combinações de números repetidos se o seu número * valor> 10. Ou seja, cortamos os vetores até que sua soma seja menor que 10 e adicionamos aqueles que são 10 ao 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 da 3ª etapa, nosso vetor será o seguinte
[1, 1, 2, 2, 2, 4, 5, 8, 9]
Como você pode ver, o tamanho do vetor diminuiu de 25 para 9, é muito menor (lembre-se do número de iterações);
Com números negativos
Isso é um pouco mais complicado. assumiremos que implementamos a função de encontrar combinações para um vetor classificado positivo com base nas restrições anteriores.
comb (arr, sum), em que sum é a quantidade necessária, arr é um vetor classificado com números positivos
Por exemplo, considere o vetor:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12 , -10, 9]
1. Quebre o vetorA = apenas valores positivos
B = apenas valores negativos
E também ver se temos valores = 0
2. ClassificarClassifique os vetores (ascendente positivo, descendente negativo)
Verifique o caso especial para números positivos (PASSO 1)
3. Verificação de positivoVerifique se há valores positivos
pente (B, 10)3. Verifique se há negativocrie combinações de todos os números negativos, mas com a restrição:
(soma dos elementos do módulo) <(soma de todos os positivos) + 10
encontramos combinações para as novas somas de referência (a soma dos elementos módulo + 10)
4. Igualdade 0Se o vetor de origem tiver um valor 0, adicionamos todas as combinações + 0 ao resultado;
Como resultado de tais limitações, em média, ao testar valores com uma matriz de 28 e 1000 testes, o ganho de tempo é quase 42%
Cuidado para não parecer nervoso. O autor não é responsável pelo sofrimento moral.function combine(arr, etalon = 10) {