指定された桁数 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    
 
      時間計算量:      お(ん*ん!)  
  
      補助スペース:      の上）