c++ - 找出总和在 a 到 b 之间的所有子序列

Question

我如何有效地找到总和介于 a 到 b 之间的所有子序列？我尝试了首先创建子序列然后检查条件是否存在于 a 和 b 之间的一般方法。这是我的尝试。

我也可以优化它吗？如果我不想打印它们。（如果打印它只会给出 O(n^3) 的复杂性

void printSubinrng(vector < int > arr, int n, int a, int b) {
  int sum = 0;
  for (int i = 0; i < n; i++) 
  {
    sum = sum + arr[i];
  }

  for (int i = 0; i < n; i++) {
    if (sum <= a && sum >= b) 
    {
      cout << arr[i] << " ";
    }
  }
}

void printSubsequences(vector < int > arr, int index, int a, int b, vector < int > subarr) {
  if (index == arr.size()) {
    int l = subarr.size();
    if (l != 0)
      printSubinrng(subarr, l, a, b);
  } else {
    printSubsequences(arr, index + 1, a, b, subarr);
    subarr.push_back(arr[index]);
    printSubsequences(arr, index + 1, a, b, subarr);
  }
  return;
}

标签： c++recursionc++17dynamic-programmingsubsequence