fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. long long maxProduct = 0;
  7. vector<long long> bestSolution;
  8.  
  9. void backtrack(long long N, long long currentSum, long long currentProduct, vector<long long>& solution, long long start) {
  10.     if (currentSum == N) {
  11.         cout << "Boi so: ";
  12.         for (long long x : solution) {
  13.             cout << x << " ";
  14.         }
  15.         cout << " -> Tich: " << currentProduct << endl;
  16.  
  17.         if (currentProduct > maxProduct) {
  18.             maxProduct = currentProduct;
  19.             bestSolution = solution;
  20.         }
  21.         return;
  22.     }
  23.  
  24.     for (long long i = start; i <= N - currentSum; ++i) {
  25.         solution.push_back(i);
  26.         backtrack(N, currentSum + i, currentProduct * i, solution, i + 1);
  27.         solution.pop_back();
  28.     }
  29. }
  30.  
  31. int main() {
  32.     long long N;
  33.     cin >> N;
  34.  
  35.     vector<long long> solution;
  36.     backtrack(N, 0, 1, solution, 1);
  37.  
  38.     cout << "Tich lon nhat: " << maxProduct << endl;
  39.     cout << "Cach phan tich tuong ung la:" << endl;
  40.     for (long long x : bestSolution) {
  41.         cout << x << " ";
  42.     }
  43.     cout << endl;
  44.  
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
20
stdout
copy 
Boi so: 1 2 3 4 10  -> Tich: 240
Boi so: 1 2 3 5 9  -> Tich: 270
Boi so: 1 2 3 6 8  -> Tich: 288
Boi so: 1 2 3 14  -> Tich: 84
Boi so: 1 2 4 5 8  -> Tich: 320
Boi so: 1 2 4 6 7  -> Tich: 336
Boi so: 1 2 4 13  -> Tich: 104
Boi so: 1 2 5 12  -> Tich: 120
Boi so: 1 2 6 11  -> Tich: 132
Boi so: 1 2 7 10  -> Tich: 140
Boi so: 1 2 8 9  -> Tich: 144
Boi so: 1 2 17  -> Tich: 34
Boi so: 1 3 4 5 7  -> Tich: 420
Boi so: 1 3 4 12  -> Tich: 144
Boi so: 1 3 5 11  -> Tich: 165
Boi so: 1 3 6 10  -> Tich: 180
Boi so: 1 3 7 9  -> Tich: 189
Boi so: 1 3 16  -> Tich: 48
Boi so: 1 4 5 10  -> Tich: 200
Boi so: 1 4 6 9  -> Tich: 216
Boi so: 1 4 7 8  -> Tich: 224
Boi so: 1 4 15  -> Tich: 60
Boi so: 1 5 6 8  -> Tich: 240
Boi so: 1 5 14  -> Tich: 70
Boi so: 1 6 13  -> Tich: 78
Boi so: 1 7 12  -> Tich: 84
Boi so: 1 8 11  -> Tich: 88
Boi so: 1 9 10  -> Tich: 90
Boi so: 1 19  -> Tich: 19
Boi so: 2 3 4 5 6  -> Tich: 720
Boi so: 2 3 4 11  -> Tich: 264
Boi so: 2 3 5 10  -> Tich: 300
Boi so: 2 3 6 9  -> Tich: 324
Boi so: 2 3 7 8  -> Tich: 336
Boi so: 2 3 15  -> Tich: 90
Boi so: 2 4 5 9  -> Tich: 360
Boi so: 2 4 6 8  -> Tich: 384
Boi so: 2 4 14  -> Tich: 112
Boi so: 2 5 6 7  -> Tich: 420
Boi so: 2 5 13  -> Tich: 130
Boi so: 2 6 12  -> Tich: 144
Boi so: 2 7 11  -> Tich: 154
Boi so: 2 8 10  -> Tich: 160
Boi so: 2 18  -> Tich: 36
Boi so: 3 4 5 8  -> Tich: 480
Boi so: 3 4 6 7  -> Tich: 504
Boi so: 3 4 13  -> Tich: 156
Boi so: 3 5 12  -> Tich: 180
Boi so: 3 6 11  -> Tich: 198
Boi so: 3 7 10  -> Tich: 210
Boi so: 3 8 9  -> Tich: 216
Boi so: 3 17  -> Tich: 51
Boi so: 4 5 11  -> Tich: 220
Boi so: 4 6 10  -> Tich: 240
Boi so: 4 7 9  -> Tich: 252
Boi so: 4 16  -> Tich: 64
Boi so: 5 6 9  -> Tich: 270
Boi so: 5 7 8  -> Tich: 280
Boi so: 5 15  -> Tich: 75
Boi so: 6 14  -> Tich: 84
Boi so: 7 13  -> Tich: 91
Boi so: 8 12  -> Tich: 96
Boi so: 9 11  -> Tich: 99
Boi so: 20  -> Tich: 20
Tich lon nhat: 720
Cach phan tich tuong ung la:
2 3 4 5 6
https://ideone.com/JFKiCI
language:
C++ (gcc 8.3)
created:
8 hours 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!