时间戳

首页 > 解决方案 > 使用 4 个列表，创建一个包含所有总和的列表

c++ - 使用 4 个列表，创建一个包含所有总和的列表

问题描述

我是 C++ 的初学者，一直试图从 4 个不同的数字列表中获取所有总和的输出。我想知道每个列表中最多使用 1 的所有可能总和。可以省略重复。

例如输入[1, 2], [1, 3], [2, 3], [2, -1]应该输出[-1, 0, 1, 2, 3, ... 10]。

我的列表有 4 位、6 位、6 位和 9 位长，这会有所不同吗？

我努力了

#include<bits/stdc++.h> 
using namespace std; 

void subsetSums(int arr[], int l, int r, 
                int sum=0) 
{ 
    // Print current subset 
    if (l > r) 
    { 
        cout << sum << " "; 
        return; 
    } 

    subsetSums(arr, l+1, r, sum+arr[l]); 

    subsetSums(arr, l+1, r, sum); 
} 

int main() 
{ 
    int arr[] = {7, 14, 21, 28}, {-10, -20, -30, -40, -50, -60}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    subsetSums(arr, 0, n-1); 
    return 0; 
}

但它只会产生一个错误：

expected unqualified-id before ‘{’ token
int arr[] = {5, 4, 3}, {4, -1, 5};

标签： c++

解决方案

最简单的机制是创建一个包含所有可能总和的数组，然后删除重复项。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<std::vector<int>> arrs = {
    {7, 14, 21, 28},
    {-10, -20, -30, -40, -50, -60},
    {50, 90}
  };

  // Let's start with 0 in the results, as if we used no value from any of
  // the arrays
  std::vector<int> results = {0};

  // Append new sums to the results list
  for (const auto &arr : arrs) {
    const int length = results.size();
    for (int i = 0; i < length; i++)
      for (int j = 0; j < arr.size(); j++)
        results.push_back(results[i] + arr[j]);
  }

  // Remove duplicates
  std::sort(results.begin(), results.end());
  results.erase(
    std::unique(results.begin(), results.end()),
    results.end());

  // Print the results
  for (int value : results)
    std::cout << value << " ";
  std::cout << "\n";
}

推荐阅读