从 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++ 程序。