题解 | #牛群的第 m大的和# 模拟

首先题目有误，要求的是第 m 大的和，而不是第 m 小的和

那么就保存一个大小为 m 的数组 sums ，对于数组 nums 中的每一个数，依次与 sums 中的数相加，即可得到结果

class Solution {
  private:
    void getSum(vector<int>& nums, int start, vector<int>& sums, int m) {
        int size = sums.size();
        for (int i = 0; i < size; i++) {
            sums.push_back(start + sums[i]);
        }
        if (sums.size() > m) {
            sort(sums.begin(), sums.end(), greater<>());
            sums.resize(m);
        }
    }
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param m int整型
     * @return int整型
     */
    int mthSmallestSum(vector<int>& nums, int m) {
        vector<int> sums;
        sums.emplace_back(0);
        for (int i = 0; i < nums.size(); i++) {
            getSum(nums, nums[i], sums, m);
        }
        return sums.back();
    }
};

时间复杂度：O(m*n)，其中m，n分别为 sums 和 nums 的大小，在最坏情况下，nums 的元素要进行 m 次循环

空间复杂度：O(m)，保存 sums 数组