Array example in java

Question

suppose I have an array int [] arr = {1,2,4,5,7} and also the number 6 so I need the result 01100, which means 2 + 4 = 6 in the array, so the result will be equal 1, if the number in the sum is 0, otherwise I also need the number of bits, the result will be the same number as the length of the array

I need a java method that performs this operation

Answer 1

This is very similar to the problem of the sum of the sum of the subset , i.e. given a set of integers, determine if a nonempty subset is zero. In your case, you need to determine if a nonempty subset is a specific integer. The last part about filling in a bit array is pure cosmetics.

A simple way to solve it is, although not very effective, i.e. O(2^N*N)is a loop between all possible subsets of integers in your array ( power set ) and determine if the sum of this subset is equal to the number you specified.

Answer 2

Here's how to do it recursively. As JG noted, there is no effective solution to a common 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);
}