java - java中关于数组的例子

Question

假设我有一个数组 int [] arr={1,2,4,5,7} 并且还有数字 6 所以我需要结果为 01100 这意味着数组中的 2+4=6 所以结果将如果总和中的数字为 0，则为 1，否则我还需要结果中的位数与数组长度相同

我需要执行此操作的 java 方法

Answer 1

这与子集和问题非常相似，即给定一组整数，确定非空子集是否等于零。在您的情况下，您需要确定非空子集是否等于特定整数。后面关于填充位数组的部分纯粹是化妆品。

解决它的一种简单方法 - 尽管效率不高，即- 在数组（幂集O(2^N*N)）中每个可能的整数子集之间循环，并确定该子集的总和是否等于给定的数字。

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