пример о массиве в Java

Question

предположим, что у меня есть массив int [] arr = {1,2,4,5,7}, а также номер 6 поэтому мне нужно, чтобы результат был 01100, что означает, что 2 + 4 = 6 в массиве, поэтому результат будет 1, если число в сумме 0 в противном случае также мне нужно, чтобы число битов в результате совпадало с длиной массива

Мне нужен метод Java, который выполняет эту операцию

Answer 1

Это очень похоже на проблему суммы подмножеств , т.е., учитывая набор целых чисел, определить, равен ли непустое подмножество нулю. В вашем случае вам необходимо определить, равно ли непустое подмножество определенному целому числу. Последняя часть о заполнении битового массива - это чисто косметика.

Простой способ ее решения - хотя и не очень эффективный, т. Е. 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);
}