Beispiel über Array in Java

Question

nehme an, dass ich ein Array int [] arr = {1,2,4,5,7} und auch Nummer 6 habe, so brauche ich das Ergebnis 01100 sein, das bedeutet, dass 2 + 4 = 6 in dem Array, so wird das Ergebnis 1, wenn die Zahl in der Summe 0 sonst i Länge die gleiche Anzahl wie Array auch Anzahl der Bits in dem Ergebnis muß

i benötigen Java-Methode, dass diese Operation durchführt

Answer 1

Dies ist sehr ähnlich der subset sum problem, dh, gegeben eine Menge von ganzen Zahlen, bestimmen, ob eine nicht leere Teilmenge gleich Null ist. In Ihrem Fall müssen Sie feststellen, ob eine nicht leere Untermenge einer bestimmten Ganzzahl entspricht. Der letzte Teil über das Ausfüllen der Bit-Array ist rein Kosmetika.

Ein einfacher Weg, um es zu lösen - wenn auch nicht sehr effizient, dh O(2^N*N) - ist zwischen jeder möglichen Teilmenge von ganzen Zahlen in Ihrem Array (power set) Zyklus, und bestimmen, ob die Summe dieser Teilmenge gleich der Anzahl Sie ist sind gegeben.

Answer 2

Hier ist eine Möglichkeit, es rekursiv zu tun. Wie von JG bemerkt, gibt es keine effiziente Lösung für das allgemeine Problem.

private static int[] solve(int[] arr, int target, int res[], int length, int sum) { 
    if (length == arr.length) 
     return (sum == target)? res : null; 
    res[length] = 0; 
    int[] r = solve(arr, target, res, length + 1, sum); 
    if (r != null) 
     return r; 
    res[length] = 1; 
    r = solve(arr, target, res, length + 1, sum + arr[length]); 
    if (r != null) 
     return r; 
    return null; 
} 

public static int[] solve(int[] arr, int target) { 
    return solve(arr, target, new int[arr.length], 0, 0); 
}