所有从1到n中取出的组合的乘积之和

题目描述

给定一个正整数 n，找出所有从 1 到 n 取出的数字的不同组合，将每个组合中的数字乘起来，然后将乘积加起来。

例如，若 n = 3，则结果为 (1 * 2 * 3) + (1 * 2) + (1 * 3) + (2 * 3) + 1 + 2 + 3 = 18。

请输出从 1 到 n 所有数字的不同组合的乘积之和。

题目分析

这道题目可以使用递归解法来求解。由于需要求从 1 到 n 所有数字的不同组合，因此可以通过遍历 1 到 n 的所有数字，并将其与后面的数字进行组合来获得所有组合。使用递归的方法可以将这些组合逐步拆分成更小的组合。

递归解法思路

我们可以将题目分成两个子问题：如何获取所有数字的组合和如何计算每个组合的乘积。因此我们可以设计两个递归函数。一个递归函数用于获取所有数字的组合，另一个递归函数用于计算每个组合的乘积。对于每个数字，我们可以有两种选择：要么将其添加到当前组合中，要么不添加。因此，在每个递归中，我们重复这个过程并更新组合和乘积。

代码实现

class Solution {

public:
    int sum = 0;
    int product = 1;
    int sumSubsets(int n) {
        vector currentSubset;
        int currentNumber = 1;
        getSubsets(currentNumber, n, currentSubset);
        return sum;
    }
    void getSubsets(int currentNumber, int n, vector ¤tSubset) {
        if (currentNumber > n) {
            getProduct(currentSubset);
            return;
        }
        // 不添加数字
        getSubsets(currentNumber + 1, n, currentSubset);
        // 添加数字
        currentSubset.push_back(currentNumber);
        getSubsets(currentNumber + 1, n, currentSubset);
        currentSubset.pop_back();
    }
    void getProduct(vector &subset) {
        if (subset.empty()) {
            return;
        }
        for (int i = 0; i < subset.size(); i++) {
            product *= subset[i];
        }
        sum += product;
        product = 1;
    }
};

时间复杂度

时间复杂度为 O(2^n × n)，其中 n 是输入数字。在每个递归步骤中，我们有两个选择：将当前数字添加到组合中或跳过它。因此，总共有 2^n 种选择。此外，在每个递归步骤中，我们需要遍历当前组合中的所有数字，因此时间复杂度为 O(n)。

空间复杂度

空间复杂度为 O(n)，其中 n 是输入数字。我们需要一个数组存储当前组合，并在每个递归步骤中创建新的组合。

总结

这道题目可以使用递归来解决。我们可以将问题分成两个子问题：如何获取所有数字的组合和如何计算每个组合的乘积。通过分割问题并分别解决，我们可以将它们组合在一起来获得整个问题的解决方案。我们还需要注意时间和空间复杂度，以避免浪费不必要的计算资源。