가능한 모든 하위 집합의 곱의 합계

음이 아닌 정수 n개의 배열이 주어졌습니다. 이 작업은 가능한 모든 하위 집합의 요소 곱의 합을 찾는 것입니다. 하위 집합의 숫자가 작고 컴퓨팅 제품이 연산 오버플로를 일으키지 않는다고 가정할 수 있습니다.

예 :

Input : arr[] = {1 2 3} Output : 23 Possible Subset are: 1 2 3 {1 2} {1 3} {2 3} {1 2 3} Products of elements in above subsets : 1 2 3 2 3 6 6 Sum of all products = 1 + 2 + 3 + 2 + 3 + 6 + 6 = 23

순진한 접근 방식: 간단한 접근 방식은 가능한 모든 하위 집합을 하나씩 생성 모든 요소의 합을 계산합니다. 이 접근 방식의 시간 복잡성은 총 2개이므로 기하급수적입니다.^N- 1개의 하위 집합.

안 효율적인 접근 전체 문제를 어떤 패턴으로 일반화하는 것입니다. 두 개의 숫자 a와 b가 있다고 가정합니다. 가능한 모든 하위 집합 제품을 다음과 같이 작성할 수 있습니다.

 = a + b + ab = a(1+b) + b + 1 - 1 = a(1+b) + (1+b) - 1 = (a + 1) * (b + 1) - 1 = (1+a) * (1 + b) - 1

이제 a b c 세 개의 숫자를 선택하세요.

 = a + b + c + ab + bc + ca + abc = a + ac + b + bc + ab + abc + c + 1 - 1 = a(1+c) + b(1+c) + ab(1+c) + c + 1 - 1 = (a + b + ab + 1)(1+c) - 1 = (1+a) * (1+b) * (1+c) - 1

위 패턴은 n개 숫자에 대해 일반화될 수 있습니다.

다음은 위의 아이디어를 구현한 것입니다.

C++

// C++ program to find sum of product of // all subsets. #include    using namespace std; // Returns sum of products of all subsets // of arr[0..n-1] int productOfSubsetSums(int arr[] int n) {  int ans = 1;  for (int i = 0; i < n; ++i )  ans = ans * (arr[i] + 1);  return ans-1; } // Driver code int main() {  int arr[] = {1 2 3 4};  int n = sizeof(arr)/sizeof arr[0];  cout << productOfSubsetSums(arr n);  return 0; }

Java

// Java program to find sum of product of // all subsets. public class Subset {  // Returns sum of products of all subsets  // of arr[0..n-1]  static int productOfSubsetSums(int arr[] int n)  {  int ans = 1;  for (int i = 0; i < n; ++i )  ans = ans * (arr[i] + 1);  return ans-1;  }    public static void main (String[] args)  {  int arr[] = {1 2 3 4};  int n = arr.length;  System.out.println(productOfSubsetSums(arr n));  } } // This code is contributed by Saket Kumar

Python3

# Python3 program to # find sum of product of # all subsets. # Returns sum of products # of all subsets # of arr[0..n-1] def productOfSubsetSums(arr n): ans = 1; for i in range(0n): ans = ans * (arr[i] + 1) return ans-1 # Driver code arr = [1 2 3 4] n = len(arr) print (productOfSubsetSums(arr n)) # This code is contributed # by Shreyanshi Arun.

// C# program to find sum of  // product of all subsets. using System; public class Subset {    // Returns sum of products of all   // subsets of arr[0..n-1]  static int productOfSubsetSums(int []arr int n)  {  int ans = 1;  for (int i = 0; i < n; ++i )  ans = ans * (arr[i] + 1);  return ans-1;  }    // Driver Code  public static void Main ()  {  int []arr = {1 2 3 4};  int n = arr.Length;  Console.Write(productOfSubsetSums(arr n));  } } // This code is contributed by Nitin Mittal.

PHP

 // PHP program to find sum of  // product of all subsets. // Returns sum of products of  // all subsets of arr[0..n-1] function productOfSubsetSums($arr $n) { $ans = 1; for ($i = 0; $i < $n; ++$i ) $ans = $ans * ($arr[$i] + 1); return $ans-1; } // Driver code $arr = array(1 2 3 4); $n = sizeof($arr); echo(productOfSubsetSums($arr $n)); // This code is contributed by Ajit. ?>

JavaScript

<script> // Javascript program to find sum of product of  // all subsets.  // Returns sum of products of all subsets  // of arr[0..n-1]  function productOfSubsetSums(arr n)  {   let ans = 1;   for (let i = 0; i < n; ++i )   ans = ans * (arr[i] + 1);   return ans-1;  }  // Driver code   let arr = [1 2 3 4];   let n = arr.length;   document.write(productOfSubsetSums(arr n));  // This code is contributed by Mayank Tyagi </script>

산출

시간 복잡도: O(n)
보조 공간: O(1)

퀴즈 만들기