fork(2) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<vector<int>> generate(int pos, int N, int mn_sum, vector<pair<int, int>> &a) {
  5.     if (N < mn_sum || pos >= a.size()) return {};
  6.     vector<vector<int>> ret;
  7.     pair<int, int> p = a[pos];
  8.     if (pos == a.size() - 1 && N <= p.second) {
  9.         ret.push_back({N});
  10.         return ret;
  11.     }
  12.     int mn = p.first, mx = p.second;
  13.     for (int i = mn; i <= mx; i++) {
  14.         auto cur = generate(pos + 1, N - i, mn_sum - mn, a);
  15.         for (auto c: cur) {
  16.             c.insert(c.begin(), i);
  17.             ret.push_back(c);
  18.         }
  19.     }
  20.     return ret;
  21. }
  22.  
  23. int main() {
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(0);
  26.     int N; // input given by user
  27.     cin >> N;
  28.     vector<pair<int, int>> a = {{25, 30}, {25, 30}, {17, 20}, {5, 10}, {8, 10}};
  29.     int mn_sum = 0;
  30.     for (auto p: a) mn_sum += p.first;
  31.  
  32. 	//generate all possible solutions
  33.     auto res = generate(0, N, mn_sum, a);
  34.  
  35.     if (res.size() == 0) {
  36.         cout << "No answer possible for the given N" << "\n";
  37.     } else {
  38.         //randomly pick one answer between 0 and res.size()
  39.         //you can replace this with any desired probability distribution methods
  40.         srand(time(NULL)); // Seed the time
  41.         int rand_num = rand() % (res.size());
  42.         for (int v: res[rand_num]) 
  43.             cout << v << " ";
  44.         cout << "\n";
  45.     }
  46.  
  47.     return 0;
  48. }
Success #stdin #stdout 0.01s 5440KB
comments (?)
stdin 
81
stdout 
25 25 18 5 8
https://ideone.com/QoWXzZ
language:
C++14 (clang 8.0)
created:
2 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!