Algoritmo

Programação Java
#1

Pessoal,

vê se alguém consegue me ajuda com esse algoritmo.
Uma rotina que receba um conjunto de entradas, por exemplo,
1-2-3-4-5-6 (6 entradas), e um total, por exemplo 7.
A rotina deve responder quais entradas combinadas (somadas) atingem o valor total, ou seja, 1+2+4, 3+4, e 1+6.

Andei observando que são muitas possibilidades, no caso a quantidade de entradas pode chegar a 36.

Obrigado pela ajuda.

#2

Combinadas 2 a 2?

[edit]

desculpa, acabei de ver que pode ser qq quantidade :smiley:

#3

Olá!

Você pode fazer isso usando backtracking, isto é, recursividade!

Atente para o fato de que adição é comutativa, assim 2 + 3 = 3 + 2.

Procure por algorítmos para análise combinatória.

Mais dica que isso, só no google :slight_smile:

Abraço!

#4

sugestão:

ordene as suas entradas de forma crescente.

imagine q vc tem

1 2 4 5 9
total: 6

vc tem 1 + 5 e 2 + 4, porem vc não precisa comparar o 9, compreendeu.

  • pegue o “primeiro” número SE for menor que total
  • pegue o proximo número
  • se o proximo é menor ou igual a (total - primeiro) compare soma.
    se for maior interrompe.

vai dar uma agilidade ao seu algoritmo.

#5