배열의 모든 가능한 하위 집합의 합이

Question

배열의 가능한 모든 하위 집합의 합을 구하는 코드를 작성했습니다. 예상되는 출력을 얻고 있지만 시간과 관련된 테스트 사례를 지울만큼 빠르지 못합니다.

속도에 맞게 코드를 최적화 할 수있는 사람이 있습니까?

첫 번째 입력 (testcases)은 테스트 케이스의 수입니다. 테스트 케이스의 수에 따라 array (size) 및 array 요소 (set)의 크기를 갖습니다.

예를 들어, 유효한 입력 될 것이다 :

1은을 testcases의 개수 :

1 
3 
2 3 5 

. 3은 테스트 세트의 크기이고 2 3 5은 입력 세트의 요소입니다.

예상 출력은 다음

는

71

상기 출력 값의 계산은 다음

{2}, {3}, {5}, {2, 3}, {3, 5}, {2, 5}, {2, 3, 5} 

=> 2 3 5  6  15  10  30 

=> 2 + 3 + 5 + 6 + 15 + 10 + 30 

=> 71 

---

import java.util.Scanner; 

public class Test { 
    static int printSubsets(int set[]) { 
     int n = set.length; 
     int b = 0; 

     for (int i = 0; i < (1 << n); i++) { 
      int a = 1; 
      for (int j = 0; j < n; j++){ 

       if ((i & (1 << j)) > 0) { 

        a *= set[j]; 
       }} 

      b += a; 
     } 
     return b; 
    } 

    public static void main(String[] args) { 

     Scanner scanner = new Scanner(System.in); 
     int testCases = scanner.nextInt(); 

     for (int i = 0; i < testCases; i++) { 
      int size = scanner.nextInt(); 
      int set[] = new int[size]; 
      for (int j = 0; j < set.length; j++) { 
       set[j] = scanner.nextInt(); 
      } 

      int c = printSubsets(set); 
      System.out.println((c - 1)); 

     } 
     scanner.close(); 
    } 
} 

Answer 1

작은 수학을 사용해야합니다. 예를 들어 3 가지 값을 가질 수 있지만 A, B 및 C과 같이 호출 할 수 있습니다.

제품의 합계를 얻으려면, 당신이 계산해야 우리가 A + B + A*B 먼저 계산하면 Result2 그것을 호출,

Result3 = A + B + C + A*B + A*C + B*C + A*B*C 
     = A + B + A*B + (1 + A + B + A*B) * C 

를 이제, 당신이 얻을 :

Result2 = A + B + A*B 
Result3 = Result2 + (1 + Result2) * C 

을 우리가 반복, so

Result2 = A + (1 + A) * B 
Result1 = A 
Result2 = Result1 + (1 + Result1) * B 

패턴을 볼 수 있습니까? 의 4 개 값으로 그것을 사용하자 :

Result4 = A + B + C + D + A*B + A*C + A*D + B*C + B*D + C*D 
     + A*B*C + A*B*D + A*C*D + B*C*D + A*B*C*D 
     =  A + B + C + A*B + A*C + B*C + A*B*C 
     + (1 + A + B + C + A*B + A*C + B*C + A*B*C) * D 
     = Result3 + (1 + Result3) * D 

요약 :

Result1 = A 
Result2 = Result1 + (1 + Result1) * B 
Result3 = Result2 + (1 + Result2) * C 
Result4 = Result3 + (1 + Result3) * D 

코드,이는 다음과 같습니다

private static long sumProduct(int... input) { 
    long result = 0; 
    for (int value : input) 
     result += (result + 1) * value; 
    return result; 
} 

하나의 반복, 그래서 O (n)이.

테스트

System.out.println(sumProduct(2, 3)); 
System.out.println(sumProduct(2, 3, 5)); 
System.out.println(sumProduct(2, 3, 5, 7)); 

출력

11 
71 
575 

UPDATE

코드도 사용 람다 표현식으로 자바 8 개 스트림을 사용하여 수행 할 수 있습니다

중 하나 IntStream.of(int...) 또는(그들은 똑같이합니다).

// Using IntStream with result as int 
private static int sumProduct(int... input) { 
    return IntStream.of(input).reduce((a, b) -> a + (1 + a) * b).getAsInt(); 
} 

// Using Arrays with result as long 
private static long sumProduct(int... input) { 
    return Arrays.stream(input) 
       .asLongStream() 
       .reduce((a, b) -> a + (1 + a) * b) 
       .getAsLong(); 
}