Задано число цифр n. Вивести всі n-цифрові числа, сума цифр яких дорівнює заданій сумі. Рішення не повинно розглядати початкові 0 як цифри.
приклади:  
 

    Input:      N = 2 Sum = 3   
    Output:      12 21 30   
    Input:      N = 3 Sum = 6   
    Output:      105 114 123 132 141 150 204    
  213 222 231 240 303 312 321    
  330 402 411 420 501 510 600    
    Input:      N = 4 Sum = 3   
    Output:      1002 1011 1020 1101 1110 1200   
  2001 2010 2100 3000    
  
  
    
  
  
 А     просте рішення    буде генерувати всі N-значні числа та друкувати числа, сума цифр яких дорівнює заданій сумі. Складність цього рішення буде експоненціальною.    
    Краще рішення    полягає у створенні лише тих N-значних чисел, які задовольняють заданим обмеженням. Ідея полягає у використанні рекурсії. В основному ми заповнюємо всі цифри від 0 до 9 у поточну позицію та зберігаємо суму цифр до цього часу. Потім ми рекурсивно шукаємо решту суми та кількість цифр, що залишилися. Ми обробляємо початкові 0 окремо, оскільки вони не вважаються цифрами.   
 Нижче наведена проста рекурсивна реалізація вищезазначеної ідеї –   
    
 C++   
   // A C++ recursive program to print all n-digit   // numbers whose sum of digits equals to given sum   #include          using     namespace     std  ;   // Recursive function to print all n-digit numbers   // whose sum of digits equals to given sum   // n sum --> value of inputs   // out --> output array   // index --> index of next digit to be filled in   // output array   void     findNDigitNumsUtil  (  int     n       int     sum       char  *     out        int     index  )   {      // Base case      if     (  index     >     n     ||     sum      <     0  )      return  ;      // If number becomes N-digit      if     (  index     ==     n  )      {      // if sum of its digits is equal to given sum      // print it      if  (  sum     ==     0  )      {      out  [  index  ]     =     ''  ;      cout      < <     out      < <     ' '  ;      }      return  ;      }      // Traverse through every digit. Note that      // here we're considering leading 0's as digits      for     (  int     i     =     0  ;     i      <=     9  ;     i  ++  )      {      // append current digit to number      out  [  index  ]     =     i     +     '0'  ;      // recurse for next digit with reduced sum      findNDigitNumsUtil  (  n       sum     -     i       out       index     +     1  );      }   }   // This is mainly a wrapper over findNDigitNumsUtil.   // It explicitly handles leading digit   void     findNDigitNums  (  int     n       int     sum  )   {      // output array to store N-digit numbers      char     out  [  n     +     1  ];      // fill 1st position by every digit from 1 to 9 and      // calls findNDigitNumsUtil() for remaining positions      for     (  int     i     =     1  ;     i      <=     9  ;     i  ++  )      {      out  [  0  ]     =     i     +     '0'  ;      findNDigitNumsUtil  (  n       sum     -     i       out       1  );      }   }   // Driver program   int     main  ()   {      int     n     =     2       sum     =     3  ;      findNDigitNums  (  n       sum  );      return     0  ;   }   
  Java   
   // Java recursive program to print all n-digit   // numbers whose sum of digits equals to given sum   import     java.io.*  ;   class   GFG      {      // Recursive function to print all n-digit numbers      // whose sum of digits equals to given sum          // n sum --> value of inputs      // out --> output array      // index --> index of next digit to be       // filled in output array      static     void     findNDigitNumsUtil  (  int     n       int     sum       char     out  []        int     index  )      {      // Base case      if     (  index     >     n     ||     sum      <     0  )      return  ;          // If number becomes N-digit      if     (  index     ==     n  )      {      // if sum of its digits is equal to given sum      // print it      if  (  sum     ==     0  )      {      out  [  index  ]     =     ''     ;      System  .  out  .  print  (  out  );      System  .  out  .  print  (  ' '  );      }      return  ;      }          // Traverse through every digit. Note that      // here we're considering leading 0's as digits      for     (  int     i     =     0  ;     i      <=     9  ;     i  ++  )      {      // append current digit to number      out  [  index  ]     =     (  char  )(  i     +     '0'  );          // recurse for next digit with reduced sum      findNDigitNumsUtil  (  n       sum     -     i       out       index     +     1  );      }      }          // This is mainly a wrapper over findNDigitNumsUtil.      // It explicitly handles leading digit      static     void     findNDigitNums  (  int     n       int     sum  )      {      // output array to store N-digit numbers      char  []     out     =     new     char  [  n     +     1  ]  ;          // fill 1st position by every digit from 1 to 9 and      // calls findNDigitNumsUtil() for remaining positions      for     (  int     i     =     1  ;     i      <=     9  ;     i  ++  )      {      out  [  0  ]     =     (  char  )(  i     +     '0'  );      findNDigitNumsUtil  (  n       sum     -     i       out       1  );      }      }          // driver program to test above function      public     static     void     main     (  String  []     args  )         {      int     n     =     2       sum     =     3  ;      findNDigitNums  (  n       sum  );      }   }   // This code is contributed by Pramod Kumar   
  Python 3   
   # Python 3 recursive program to print    # all n-digit numbers whose sum of    # digits equals to given sum   # Recursive function to print all    # n-digit numbers whose sum of    # digits equals to given sum   # n sum --> value of inputs   # out --> output array   # index --> index of next digit to be    # filled in output array   def   findNDigitNumsUtil  (  n     sum     out    index  ):   # Base case   if   (  index   >   n   or   sum    <   0  ):   return   f   =   ''   # If number becomes N-digit   if   (  index   ==   n  ):   # if sum of its digits is equal   # to given sum print it   if  (  sum   ==   0  ):   out  [  index  ]   =   '    '   for   i   in   out  :   f   =   f   +   i   print  (  f     end   =   ' '  )   return   # Traverse through every digit. Note    # that here we're considering leading   # 0's as digits   for   i   in   range  (  10  ):   # append current digit to number   out  [  index  ]   =   chr  (  i   +   ord  (  '0'  ))   # recurse for next digit with reduced sum   findNDigitNumsUtil  (  n     sum   -   i     out     index   +   1  )   # This is mainly a wrapper over findNDigitNumsUtil.   # It explicitly handles leading digit   def   findNDigitNums  (   n     sum  ):   # output array to store N-digit numbers   out   =   [  False  ]   *   (  n   +   1  )   # fill 1st position by every digit    # from 1 to 9 and calls findNDigitNumsUtil()    # for remaining positions   for   i   in   range  (  1     10  ):   out  [  0  ]   =   chr  (  i   +   ord  (  '0'  ))   findNDigitNumsUtil  (  n     sum   -   i     out     1  )   # Driver Code   if   __name__   ==   '__main__'  :   n   =   2   sum   =   3   findNDigitNums  (  n     sum  )   # This code is contributed    # by ChitraNayal   
  C#   
   // C# recursive program to print all n-digit   // numbers whose sum of digits equals to   // given sum   using     System  ;   class     GFG     {          // Recursive function to print all n-digit      // numbers whose sum of digits equals to      // given sum      // n sum --> value of inputs      // out --> output array      // index --> index of next digit to be       // filled in output array      static     void     findNDigitNumsUtil  (  int     n       int     sum        char     []  ou       int     index  )      {      // Base case      if     (  index     >     n     ||     sum      <     0  )      return  ;      // If number becomes N-digit      if     (  index     ==     n  )      {      // if sum of its digits is equal to      // given sum print it      if  (  sum     ==     0  )      {      ou  [  index  ]     =     ''  ;      Console  .  Write  (  ou  );      Console  .  Write  (  ' '  );      }          return  ;      }      // Traverse through every digit. Note      // that here we're considering leading      // 0's as digits      for     (  int     i     =     0  ;     i      <=     9  ;     i  ++  )      {      // append current digit to number      ou  [  index  ]     =     (  char  )(  i     +     '0'  );      // recurse for next digit with      // reduced sum      findNDigitNumsUtil  (  n       sum     -     i       ou        index     +     1  );          }      }      // This is mainly a wrapper over       // findNDigitNumsUtil. It explicitly      // handles leading digit      static     void     findNDigitNums  (  int     n       int     sum  )      {          // output array to store N-digit      // numbers      char     []  ou     =     new     char  [  n     +     1  ];      // fill 1st position by every digit      // from 1 to 9 and calls       // findNDigitNumsUtil() for remaining       // positions      for     (  int     i     =     1  ;     i      <=     9  ;     i  ++  )      {      ou  [  0  ]     =     (  char  )(  i     +     '0'  );      findNDigitNumsUtil  (  n       sum     -     i       ou       1  );      }      }          // driver program to test above function      public     static     void     Main     ()         {      int     n     =     2       sum     =     3  ;          findNDigitNums  (  n       sum  );      }   }   // This code is contributed by nitin mittal.   
  JavaScript   
    <  script  >   // Javascript recursive program to print all n-digit   // numbers whose sum of digits equals to given sum          // Recursive function to print all n-digit numbers      // whose sum of digits equals to given sum          // n sum --> value of inputs      // out --> output array      // index --> index of next digit to be       // filled in output array      function     findNDigitNumsUtil  (  n       sum       out       index  )      {          // Base case      if     (  index     >     n     ||     sum      <     0  )      return  ;          // If number becomes N-digit      if     (  index     ==     n  )      {          // if sum of its digits is equal to given sum      // print it      if  (  sum     ==     0  )      {      out  [  index  ]     =     ''  ;      for  (  let     i     =     0  ;     i      <     out  .  length  ;     i  ++  )          document  .  write  (  out  [  i  ]);      document  .  write  (  ' '  );      }      return  ;      }          // Traverse through every digit. Note that      // here we're considering leading 0's as digits      for     (  let     i     =     0  ;     i      <=     9  ;     i  ++  )      {      // append current digit to number      out  [  index  ]     =     String  .  fromCharCode  (  i     +     '0'  .  charCodeAt  (  0  ));          // recurse for next digit with reduced sum      findNDigitNumsUtil  (  n       sum     -     i       out       index     +     1  );      }      }          // This is mainly a wrapper over findNDigitNumsUtil.      // It explicitly handles leading digit      function     findNDigitNums  (  n    sum  )      {      // output array to store N-digit numbers      let     out     =     new     Array  (  n  +  1  );      for  (  let     i  =  0  ;  i   <  n  +  1  ;  i  ++  )      {      out  [  i  ]  =  false  ;      }      // fill 1st position by every digit from 1 to 9 and      // calls findNDigitNumsUtil() for remaining positions      for     (  let     i     =     1  ;     i      <=     9  ;     i  ++  )      {      out  [  0  ]     =     String  .  fromCharCode  (  i     +     '0'  .  charCodeAt  (  0  ));      findNDigitNumsUtil  (  n       sum     -     i       out       1  );      }      }          // driver program to test above function      let     n     =     2       sum     =     3  ;      findNDigitNums  (  n       sum  );          // This code is contributed by avanitrachhadiya2155    <  /script>   
  PHP   
      // A PHP recursive program to print all    // n-digit numbers whose sum of digits    // equals to given sum   // Recursive function to print all n-digit   // numbers whose sum of digits equals to    // given sum   // n sum --> value of inputs   // out --> output array   // index --> index of next digit to be    // filled in output array   function   findNDigitNumsUtil  (  $n     $sum     $out     $index  )   {   // Base case   if   (  $index   >   $n   ||   $sum    <   0  )   return  ;   // If number becomes N-digit   if   (  $index   ==   $n  )   {   // if sum of its digits is equal    // to given sum print it   if  (  $sum   ==   0  )   {   $out  [  $index  ]   =   ''  ;   foreach   (  $out   as   &  $value  )   print  (  $value  );   print  (  ' '  );   }   return  ;   }   // Traverse through every digit. Note    // that here we're considering leading   // 0's as digits   for   (  $i   =   0  ;   $i    <=   9  ;   $i  ++  )   {   // append current digit to number   $out  [  $index  ]   =   chr  (  $i   +   ord  (  '0'  ));   // recurse for next digit with    // reduced sum   findNDigitNumsUtil  (  $n     $sum   -   $i     $out     $index   +   1  );   }   }   // This is mainly a wrapper over findNDigitNumsUtil.   // It explicitly handles leading digit   function   findNDigitNums  (  $n     $sum  )   {   // output array to store N-digit numbers   $out   =   array_fill  (  0     $n   +   1     false  );   // fill 1st position by every digit from    // 1 to 9 and calls findNDigitNumsUtil()    // for remaining positions   for   (  $i   =   1  ;   $i    <=   9  ;   $i  ++  )   {   $out  [  0  ]   =   chr  (  $i   +   ord  (  '0'  ));   findNDigitNumsUtil  (  $n     $sum   -   $i     $out     1  );   }   }   // Driver Code   $n   =   2  ;   $sum   =   3  ;   findNDigitNums  (  $n     $sum  );   // This code is contributed    // by chandan_jnu   ?>   
   
    Вихід:        
    
  
 12 21 30    
 
      Часова складність:      О (н*н!)  
  
      Допоміжний простір:      O(n)