fork download
copy 
  1. /******************************************************************************
  2.  
  3.                               Online C++ Compiler.
  4.                Code, Compile, Run and Debug C++ program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9.  
  10. #include <iostream>
  11. #include <vector>
  12. #include <sstream>
  13. #include <cassert>
  14.  
  15. void Rec(std::vector<int>& arr, int k, int start, int depth, std::vector<int>& indices) {
  16.     int n = arr.size();
  17.     if (depth == k) {
  18.         int sum = 0;
  19.         for (int idx : indices) {
  20.             sum += arr[idx];
  21.         }
  22.         if (sum == 0) {
  23.             for (int idx : indices) {
  24.                 std::cout << idx << " ";
  25.             }
  26.             std::cout << std::endl;
  27.         }
  28.         return;
  29.     }
  30.     for (int i = start; i < n; ++i) {
  31.         indices.push_back(i);
  32.         Rec(arr, k, i + 1, depth + 1, indices);
  33.         indices.pop_back();
  34.     }
  35. }
  36.  
  37. void findSubarrays(std::vector<int>& arr, int k) {
  38.     std::vector<int> indices;
  39.     Rec(arr, k, 0, 0, indices);
  40. }
  41.  
  42. std::string captureOutput(std::vector<int> arr, int k) {
  43.     std::ostringstream buffer;
  44.     std::streambuf* prevcoutbuf = std::cout.rdbuf(buffer.rdbuf());
  45.     //buffer — строковый поток, куда будет направляться вывод вместо std::cout.
  46.     //prevcoutbuf сохраняет стандартный поток вывода, чтобы потом его вернуть.
  47.     findSubarrays(arr, k);
  48.     std::cout.rdbuf(prevcoutbuf);
  49.     return buffer.str();
  50. }
  51.  
  52. void runTests() {
  53.     // Все нули
  54.     {
  55.         std::vector<int> arr = {0, 0, 0};
  56.         int k = 2;
  57.         std::string output = captureOutput(arr, k);
  58.         assert(!output.empty() && "Test 1 failed");
  59.     }
  60.  
  61.     // Нет подмножеств с суммой 0
  62.     {
  63.         std::vector<int> arr = {1, 2, 3};
  64.         int k = 2;
  65.         std::string output = captureOutput(arr, k);
  66.         assert(output.empty() && "Test 2 failed");
  67.     }
  68.  
  69.     // Есть подмножество с суммой 0
  70.     {
  71.         std::vector<int> arr = {1, -1, 2, -2};
  72.         int k = 2;
  73.         std::string output = captureOutput(arr, k);
  74.         assert(!output.empty() && "Test 3 failed");
  75.     }
  76.  
  77.     // Один элемент 0
  78.     {
  79.         std::vector<int> arr = {0};
  80.         int k = 1;
  81.         std::string output = captureOutput(arr, k);
  82.         assert(!output.empty() && "Test 4 failed");
  83.     }
  84.  
  85.     //  Большие значения
  86.     {
  87.         std::vector<int> arr = {1000000, -1000000, 500000, -500000};
  88.         int k = 2;
  89.         std::string output = captureOutput(arr, k);
  90.         assert(!output.empty() && "Test 5 failed");
  91.     }
  92.  
  93.     // Пустой массив
  94.     {
  95.         std::vector<int> arr = {};
  96.         int k = 1;
  97.         std::string output = captureOutput(arr, k);
  98.         assert(output.empty() && "Test 6 failed");
  99.     }
  100.  
  101.     // k больше, чем размер массива
  102.     {
  103.         std::vector<int> arr = {1, -1};
  104.         int k = 3;
  105.         std::string output = captureOutput(arr, k);
  106.         assert(output.empty() && "Test 7 failed");
  107.     }
  108.  
  109.     std::cout << "All tests passed!\n";
  110. }
  111.  
  112. int main() {
  113.     runTests();
  114.  
  115.     int n, k;
  116.     std::cin >> n;
  117.     std::cin >> k;
  118.  
  119.     std::vector<int> arr(n);
  120.     for (int i = 0; i < n; ++i) {
  121.         std::cin >> arr[i];
  122.     }
  123.     findSubarrays(arr, k);
  124. }
  125.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
12
6
1
2
3
4
5
-15
3
3
3
3
-3
-3
stdout
copy 
All tests passed!
0 1 2 3 4 5 
0 1 3 4 5 6 
0 1 3 4 5 7 
0 1 3 4 5 8 
0 1 3 4 5 9 
0 2 4 5 6 7 
0 2 4 5 6 8 
0 2 4 5 6 9 
0 2 4 5 7 8 
0 2 4 5 7 9 
0 2 4 5 8 9 
0 4 5 6 7 8 
0 4 5 6 7 9 
0 4 5 6 8 9 
0 4 5 7 8 9 
1 2 3 5 6 7 
1 2 3 5 6 8 
1 2 3 5 6 9 
1 2 3 5 7 8 
1 2 3 5 7 9 
1 2 3 5 8 9 
1 3 5 6 7 8 
1 3 5 6 7 9 
1 3 5 6 8 9 
1 3 5 7 8 9 
2 5 6 7 8 9
https://ideone.com/1COzpc
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!