fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // В качестве первого слагаемого мы можем выбрать любое число K
  7. // из диапазова [1..N]. Тогда останется решить задачу размера
  8. // N-K при условиии что максимальное слагаемое будет не больше
  9. // чем выбранное на данном шаге
  10.  
  11.  
  12. namespace {
  13.  
  14. void PrintArray(const vector<unsigned int> &acc)
  15. {
  16.     for (unsigned int i = 0; i < acc.size(); ++i) {
  17.         if (i) {
  18.             cout << " + ";
  19.         }
  20.         cout << acc[i];
  21.     }
  22.     cout << "\n";
  23. }
  24.  
  25. void Helper(vector<unsigned int>& acc, unsigned int max, unsigned int remain) {
  26.     if (remain == 0) {
  27.         PrintArray(acc);
  28.         return;
  29.     }
  30.  
  31.     acc.push_back(0);
  32.  
  33.     for (auto i = std::min(max, remain); i > 0; --i) {
  34.         acc.back() = i;
  35.         Helper(acc, i, remain - i);
  36.     }
  37.  
  38.     acc.pop_back();
  39. }
  40.  
  41. }
  42.  
  43. void PrintAllPartitions(unsigned int N)
  44. {
  45.     vector<unsigned int> res;
  46.     res.reserve(N);
  47.     Helper(res, N , N);
  48. }
  49.  
  50.  
  51. int main()
  52. {
  53.     PrintAllPartitions(4);
  54.     return 0;
  55. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
https://ideone.com/EMbfJd
language:
C++14 (gcc 8.3)
created:
7 years 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!