Alle Zahlen, die sich aus dem Hinzufügen von Elementen eines Arrays ergeben

Question

Ich versuche ein Programm zu erstellen, das bei einem Array von Ganzzahlen alle Werte zurückgibt, die sich aus dem Hinzufügen von Vektorelementen ergeben.

Zum Beispiel: für ein Array A = {2,1,3} Die Ausgabe sein sollte {2,3,5,1,3,4,3,5,4,6}

Ich brauche zu programmieren, die rohe Gewalt iterativ verwendet wird, habe ich versucht, es mit mehreren for-Schleifen verschachtelt zu lösen, aber ich hatte Erfolg nicht

Answer 1

Offensichtlich da die Ausgangsgröße 2^n sein wird, wo n die Anzahl der Elemente in Eingangsvektor ist, wird dies ziemlich bald über genügend Arbeitsspeicher ausgeführt.

Das heißt, Sie suchen nach der Summe aller Kombinationen von Elementen im Vektor. Alles, was Sie tun müssen, ist alle Kombinationen zu finden. Eine einfache Möglichkeit besteht darin, von 0 to 2^n zu iterieren und in jeder Iteration nur die Indizes aus dem Vektor auszuwählen, für die Bits im Iterationszähler eingeschaltet sind.

Hier ist eine Brute-Force-Methode

package com.test; 

import java.util.Arrays; 

public class TestCombo { 
    public static void main(String[] args) { 
     int[] arr = {2, 1, 3}; 

     int resultCount = (int)Math.pow(2, arr.length); 
     int[] result = new int[resultCount - 1]; 

     for(int i = 1; i < result.length + 1; i++) { 
      int j = i; 

      int sum = 0; 

      for(int arrI = 0; j != 0; arrI++) { 
       if((j & 1) == 1) { //Is arrI bit turned on? 
        sum += arr[arrI]; 
       } 

       j = j >> 1; 
      } 

      result[i-1] = sum; 
     } 

     Arrays.stream(result).forEach(System.out::println);; 
    } 
} 

Answer 2

ich würde

List<Integer> combos(int[] input) 
{ 
    return combos(input, 0); 
} 

List<Integer> combos(int[] input, int offset) 
{ 
    if(offset >= input.length) //base case, return 0 for no elements added 
    { 
     List<Integer> out = new ArrayList<Integer>((int)Math.pow(2, input.length)); 
     out.add(0); 
     return out; 
    } 

    List<Integer> prev = combos(input, offset + 1); 
    prev.addAll(prev); //double the previous result 

    //add input[offset] to half the elements 
    for(int i = 0; i < prev.size()/2; i++) 
     prev.set(i, prev.get(i) + input[offset]); 

    return prev; 
} 

Eingabe {1, 2, 4} gibt eine rekursive Lösung empfehlen {7, 3, 5, 1, 6, 2, 4, 0}

Beachten Sie, dass diese 0 enthält, die keines der Elemente technisch Zugabe zusammen