assume that i have an array int [] arr={1,2,4,5,7} and also have number 6 so i need the result to be 01100 that means that 2+4=6 in the array so the result will be 1 if the number in the sum 0 otherwise also i need number of bits in开发者_如何学Python the result be the same number as array lenght
i need java method that perform this operation
This is very similar to the subset sum problem, i.e., given a set of integers, determine if a non-empty subset equals zero. In your case, you need to determine if a non-empty subset equals a specific integer. The latter part about filling in the bit array is purely cosmetics.
A simple way to solve it -- albeit not very efficient, i.e., O(2^N*N)
-- is to cycle between every possible subset of integers in your array (power set), and determine if the sum of this subset equals the number you are given.
Here is a way to do it recursively. As noted by JG, there is no efficient solution for the general 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);
}
精彩评论