자바에 배열에 대한 예제

Question

배열 int [] arr = {1,2,4,5,7} 가정하고 또한 숫자 6 그래서 01100 될 결과가 필요합니다 2 + 4 = 6 배열의 결과는 합계의 개수는 0, 그렇지 나가 어레이 아이폰에 동일한 숫자 결과 내의 비트 수를 필요로하는 경우 일 수 있도록

이런 작업을 수행하는 자바 메소드 필요

Answer 1

이것은 subset sum problem과 매우 유사합니다. 즉, 정수 세트를 주면 비어 있지 않은 부분 집합이 0인지 확인합니다. 귀하의 경우, 비어 있지 않은 부분 집합이 특정 정수와 같은지 여부를 결정해야합니다. 비트 배열을 채우는 것에 대한 후반 부분은 순전히 화장품입니다.

매우 효율적인 것은 아니지만 간단한 해결 방법, 즉 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); 
}