例javaの配列

Question

配列int [] arr = {1,2,4,5,7}と数字6を持っていると仮定します。 したがって、結果は01100で2 + 4 = 6アレイ内の結果は、合計で数も0さもなければ iは、アレイな長さと同じ数である結果のビット数を必要とする場合は1になるよう

私はこの操作を実行するJavaメソッドを必要

Answer 1

これは、subset sum problemと非常によく似ています。つまり、整数のセットを指定すると、空でないサブセットがゼロに等しいかどうかを判断できます。あなたの場合、空でないサブセットが特定の整数に等しいかどうかを判断する必要があります。ビット配列を埋めることについての後半は純粋に化粧品です。

それを解決するための簡単な方法 - とはいえない、非常に効率的な、すなわち、O(2^N*N) - あなたの配列内の整数のすべての可能なサブセット間のサイクル（power set）にあり、そしてこのサブセットの合計が数あなたに等しいかどうかを判断与えられる。

Answer 2

これは再帰的に行う方法です。 JGが指摘したように、一般的な問題に対する効率的な解決策はない。

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); 
}