logo

TechCodeview

Gibt alle n-stelligen Zahlen aus, deren Ziffernsumme der angegebenen Summe entspricht

Bei gegebener Ziffernzahl n werden alle n-stelligen Zahlen ausgegeben, deren Ziffernsumme die gegebene Summe ergibt. Die Lösung sollte führende Nullen nicht als Ziffern betrachten.
Beispiele:  
 

    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


 



lexikographische Ordnung


A einfache Lösung würde darin bestehen, alle N-stelligen Zahlen zu generieren und Zahlen zu drucken, deren Ziffernsumme der angegebenen Summe entspricht. Die Komplexität dieser Lösung wäre exponentiell. 
Eine bessere Lösung besteht darin, nur die N-stelligen Zahlen zu generieren, die die gegebenen Einschränkungen erfüllen. Die Idee ist, Rekursion zu verwenden. Grundsätzlich füllen wir alle Ziffern von 0 bis 9 an der aktuellen Position ein und behalten die bisherige Ziffernsumme bei. Wir rekursieren dann für die verbleibende Summe und die Anzahl der verbleibenden Ziffern. Wir behandeln führende Nullen separat, da sie nicht als Ziffern gezählt werden.
Nachfolgend finden Sie eine einfache rekursive Implementierung der obigen Idee:
 

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 outindex): # 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(nsum)  {  // 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 ?>

Ausgabe:  
 

12 21 30

Zeitkomplexität: O(n*n!)



Hilfsraum: An)