Combinações possíveis de soma a partir de uma lista

Vc consegue especificar melhor o que vc precisa, talvez dando um exemplo sem código?

Opa, o objetivo é pegar os valores que estão na lista e fazer uma soma com esses valores que resultem no valor do n “n = 10 nesse caso”.

ex: [ 2, 3, 4 ]

2 + 4 + 4 = 10
3 + 3 + 4 = 10

No primeiro algoritmo que eu fiz se eu acrescentar o numero 6 na lista [2, 3, 4, 6] ele retorna combinações com o numero 5 também que no caso não estaria na lista, o objetivo é que as combinações de soma sejam feita apenas com os numeros que estiverem na lista.

Neal

int[] v = { 2, 4, 5, 6, 9, 10 };

for ( int i = 0; i < v.length; i++ ) {
    for ( int j = i + 1; j < v.length; j++ ) {
        for ( int k = j + 1; k < v.length; k++ ) {
            if ( v[i] + v[j] + v[k] == n ) {
                // a soma da trinca é igual a n
            }
        }
    }
}

Se vc pensar em n = 0, vc tem o problema chamado ThreeSum (3SUM). A solução trivial acima é lenta para quantidades grandes de elementos que precisam ser combinados, pois o algoritmo tem crescimento cúbico. A melhoria para a ordem quadrática envolve usar busca binária para encontrar o inverso da soma de v[i] e v[j], ajustada para n caso n seja diferente de zero. Vc pode dar uma olhada aqui se quiser saber mais sobre: 3SUM - Wikipedia

tentei esse algoritmo também mas ao excluir o 5 da lista e incluir o 3, ele continua utilizando o 5 na combinação das somas.

int n = 10;
int[] v = { 2, 3, 4, 6, 9, 10 };

for ( int i = 0; i < v.length; i++ ) {
    for ( int j = i + 1; j < v.length; j++ ) {
        for ( int k = j + 1; k < v.length; k++ ) {
            if ( v[i] + v[j] + v[k] == n ) {         	           
     	            	
            }	
            int soma = i+j+k;
        	if(soma==n) 		         
        	System.out.printf("%d + %d + %d = %d \n",i,j,k, soma);
        }		        
    }		    
}

}
}

…
retornou

1 + 4 + 5 = 10
2 + 3 + 5 = 10

Neal

Primeiro você está ignorando completamente o if que verifica se a soma dos valores é 10.
Segundo, você está somando os índices e não os valores do array.

O correto é assim, como o @davidbuzatto ensinou, mas você ignorou o código dele

int n = 10;
int[] v = {2, 3, 4, 6, 9, 10};

for (int i = 0; i < v.length; i++) {
  for (int j = i + 1; j < v.length; j++) {
    for (int k = j + 1; k < v.length; k++) {
      int soma = v[i] + v[j] + v[k];
      if (soma == n) {
        System.out.printf("%d + %d + %d = %d %n", v[i], v[j], v[k], soma);
      }
    }
  }
}

Estou iniciando agora, imaginei que tinha algo errado na hora de chamar o printf, até tentei resolver sozinho mas não sabia que dava pra chamar v[ i ]…
Mas brigadão pela ajuda dos colegas, tem me ajudado muito aqui…aos poucos vou pegando o jeito.
Tentei rodar o algoritmo aqui como você sugeriu mas ele não ta imprimindo nada no console…

Neal

Prezado, esse algoritmo vai imprimir as combinações de 3 valores onde a soma seja 10.

Dentro do conjunto {2, 3, 4, 6, 9, 10} qual seria uma combinação de 3 números onde a soma seja 10?

Aqui dá a entender que um número pode ser usado mais de uma vez. Daí teria que mudar o algoritmo, pois o atual não permite repetições…

Nobres eu to tentando solucionar um desafio porém queria tentar ver até onde chego sozinho, mas creio que falta informação na forma como eu expus o problema, então vou passar exatamente como eu recebi o desafio talvez esclareça melhor o que precisa ser executado.

Dado um vetor de números e um número n. Determine a soma com o menor número de elementos entre os números do vetor mais próxima de n e também mostre os elementos que compõem a soma. Para criar a soma, utilize qualquer elemento do vetor uma ou mais vezes.

Exemplo:

Entrada de dados:

N = 10
V = [2, 3, 4]

Saída de dados:

10
[2, 4, 4]
[3, 3, 4]

Explicação:

Se N = 10 e V = [2, 3, 4] você pode utilizar as seguintes soma: [2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 4, 4] ou [3, 3, 4]. Como a quantidade de elementos em [2, 4, 4] e [3, 3, 4] é igual, os dois conjuntos devem ser mostrados.

Ahh, agora entendendo o que vc precisa fica mais fácil. Esse problema é análogo ao problema do “troco”. Dá uma olhada aqui: Understanding The Coin Change Problem With Dynamic Programming - GeeksforGeeks

O pulo do gato é usar programação dinâmica para computar todas as formas possíveis e então, para o seu caso, coletar as que tem a menor quantidade de moedas.

O problema do troco da uma luz, mas ele retorna a quantidade de possibilidades de somas, neste caso eu preciso que imprima as somas em si com o menor numero de elementos da lista.

Se você parar e com calma dar uma olhada no que o código faz, você vai conseguir identificar onde é feita essa contagem e, adivinhe só, é ali que vc vai coletar os possíveis trocos e depois escolher os que têm menos moedas. Vc mesmo disse que quer entender, então mãos na massa.

Passei um baita tempo tentando ver isso, mas falta experiência mesmo.