주어진 자릿수 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    
 
      시간 복잡도:      오(안*안!)  
  
      보조 공간:      에)