從 1 到 n 取任意個數的組合的乘積之和

---

如果一次取 1 到 n 個數字，那麼可能會有多種組合。

例如，如果我們一次取一個數字，組合的數量將是 nC1。

如果我們一次取兩個數字，組合的數量將是 nC2。因此，組合的總數將是 nC1 + nC2 +… + nCn。

要找到所有組合的總和，我們將不得不使用一種有效的方法。否則，時間和空間複雜度將變得非常高。

問題陳述

求從 1 到 N 取任意個數的組合的乘積之和。

N 是一個給定的數字。

示例

輸入

N = 4

輸出

f(1) = 10
f(2) = 35
f(3) = 50
f(4) = 24

解釋

f(x) is the sum of the product of all combinations taken x at a time.
f(1) = 1 + 2+ 3+ 4 = 10
f(2) = (1*2) + (1*3) + (1*4) + (2*3) + (2*4) + (3*4) = 35
f(3) = (1*2*3) + (1*2*4) +(1*3*4) + (2*3*4) = 50
f(4) = (1*2*3*4) = 24 

輸入

N = 5

輸出

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

暴力法

暴力法是透過遞迴生成所有組合，找到它們的乘積，然後找到相應的和。

示例遞迴 C++ 程式

下面是一個遞迴 C++ 程式，用於查詢從 1 到 N 取任意個數的組合的乘積之和。

#include <bits/stdc++.h>
using namespace std;
//sum of each combination
int sum = 0;
void create_combination(vector<int>vec, vector<int>combinations, int n, int r, int depth, int index) {
   // if we have reached sufficient depth
   if (index == r) {
      //find the product of the combination
    	int prod = 1;
    	for (int i = 0; i < r; i++)
    	prod = prod * combinations[i];
    	// add the product to sum
    	sum += prod;
    	return;
   }
   // recursion to produce a different combination
   for (int i = depth; i < n; i++) {
      combinations[index] = vec[i];
   	  create_combination(vec, combinations, n, r, i + 1, index + 1);
   }
}
//Function to print the sum of products of
//all combinations taken 1-N at a time
void get_combinations(vector<int>vec, int n) {
   for (int i = 1; i <= n; i++) {
      // vector for storing combination
         //int *combi = new int[i];
    	vector<int>combinations(i);
    	// call combination with r = i
    	// combination by taking i at a time
    	create_combination(vec, combinations, n, i, 0, 0);
    	// displaying sum of the product of combinations
    	cout << "f(" << i << ") = " << sum << endl;
        sum = 0;
    }
}
int main() {
   int n = 5;
   //creating vector of size n
   vector<int>vec(n);
   // storing numbers from 1-N in the vector
   for (int i = 0; i < n; i++)
   	vec[i] = i + 1;
   //Function call
   get_combinations(vec, n);
   return 0;
}

輸出

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

透過建立這種方法的遞迴樹，可以看出時間複雜度是指數級的。此外，許多步驟重複出現，這使得程式冗餘。因此，它效率非常低。

高效方法（動態規劃）

一個有效的解決方案是使用動態規劃並消除冗餘。

動態規劃是一種將問題分解成子問題的方法。解決子問題並將結果儲存起來以避免重複。

使用動態規劃的示例 C++ 程式

下面是一個使用動態規劃的 C++ 程式，用於查詢從 1 到 N 取任意個數的組合的和。

#include <bits/stdc++.h>
using namespace std;
//Function to find the postfix sum array
void postfix(int a[], int n) {
for (int i = n - 1; i > 0; i--)
   a[i - 1] = a[i - 1] + a[i];
}
//Function to store the previous results, so that the computations don't get repeated
void modify(int a[], int n) {
   for (int i = 1; i < n; i++)
      a[i - 1] = i * a[i];
}
//Function to find the sum of all combinations taken 1 to N at a time
void get_combinations(int a[], int n) {
   int sum = 0;
   // sum of combinations taken 1 at a time is simply the sum of the numbers 
   // from 1 - N
   for (int i = 1; i <= n; i++)
   	  sum += i;
   cout << "f(1) = " << sum <<endl;
      // Finding the sum of products for all combination
   for (int i = 1; i < n; i++) {
   	  //Function call to find the postfix array
   	  postfix(a, n - i + 1);
      // sum of products taken i+1 at a time
   	  sum = 0;
      for (int j = 1; j <= n - i; j++) {
         sum += (j * a[j]);
      }
      cout << "f(" << i + 1 << ") = " << sum <<endl;
      //Function call to modify the array for overlapping problem
      modify(a, n);
   }
}
int main() {
   int n = 5;
  int *a = new int[n];
   // storing numbers from 1 to N
   for (int i = 0; i < n; i++)
	  a[i] = i + 1;
   //Function call
   get_combinations(a, n);
   return 0;
}

輸出

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

結論

在本文中，我們討論了求從 1 到 N 取任意個數的組合的乘積之和的問題。

我們從時間複雜度為指數級的暴力法開始，然後使用動態規劃對其進行了改進。還給出了兩種方法的 C++ 程式。