STANAANDREY

pb8

Nov 9th, 2020 (edited)
310
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. int x, s, n, st[20], c[20], fr[10];
  4.  
  5. void makeCif() {
  6.     while (x) {
  7.         fr[x % 10] = 1;
  8.         x /= 10;
  9.     }
  10.     for (int i = 0; i <= 9; i++) {
  11.         if (fr[i])
  12.             c[++n] = i;
  13.     }
  14. }
  15.  
  16. void tipar(int k) {
  17.     for (int i = 1; i <= k; i++)
  18.         cout << c[st[i]] << ' ';
  19.     cout << endl;
  20. }
  21.  
  22. int valid(int k) {
  23.     return 1;
  24. }
  25.  
  26. int sol(int k) {
  27.     if (k > n)
  28.         return 0;
  29.     int sum = 0;
  30.     for (int i = 1; i <= k; i++) {
  31.         sum += c[st[i]];
  32.     }
  33.     return (s == sum);
  34. }
  35.  
  36. void bktr() {
  37.     int k = 1;
  38.     st[k] = 0;
  39.     while (k > 0) {
  40.         if (st[k] < n) {
  41.             st[k]++;
  42.             if (valid(k)) {
  43.                 if (sol(k))
  44.                     tipar(k);
  45.                 k++;
  46.                 st[k] = st[k - 1];
  47.             }
  48.         }
  49.         else
  50.             k--;
  51.     }
  52. }
  53.  
  54. int main() {
  55.     cin >> x >> s;
  56.     makeCif();
  57.     bktr();
  58.     return 0;
  59. }
  60.  
Add Comment
Please, Sign In to add comment