fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. // Function to print the contents of the given vector
  7. void printCombination(vector<int> const &out)
  8. {
  9.     for (int i: out)
  10.         cout << i << " ";
  11.  
  12.     cout << endl;
  13. }
  14.  
  15. // Recursive function to print all combination of numbers
  16. // from i to n having sum n
  17. void recurse(int i, int n, vector<int> &out)
  18. {
  19.     // if sum becomes n, print the combination
  20.     if (n == 0)
  21.         printCombination(out);
  22.  
  23.     // start from previous element in the combination till n
  24.     for (int j = i; j <= n; j++)
  25.     {
  26.         // proceed only if j not added earlier
  27.         if (std::find(out.begin(), out.end(), j) == out.end())
  28.         {
  29.             // include current element from combination
  30.             out.push_back(j);
  31.  
  32.             // recurse with reduced sum
  33.             recurse(j, n - j, out);
  34.  
  35.             // backtrack - remove current element from combination
  36.             out.pop_back();
  37.         }
  38.     }
  39. }
  40.  
  41. // main function
  42. int main()
  43. {
  44.     int n = 5;
  45.  
  46.     vector<int> out;
  47.  
  48.     // recurse all combination of numbers from 1 to n having sum n
  49.     recurse(1, n, out);
  50.  
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 4328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 4 
2 3 
5
https://ideone.com/GbQikT
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!