Un nombre donné de chiffres n imprime tous les nombres à n chiffres dont la somme des chiffres totalise la somme donnée. La solution ne doit pas considérer les 0 comme chiffres.
Exemples :
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
burak ozcivit
UN solution simple serait de générer tous les nombres à N chiffres et d'imprimer des nombres dont la somme de leurs chiffres est égale à la somme donnée. La complexité de cette solution serait exponentielle.
Une meilleure solution consiste à générer uniquement les nombres à N chiffres qui satisfont aux contraintes données. L'idée est d'utiliser la récursivité. Nous remplissons essentiellement tous les chiffres de 0 à 9 dans la position actuelle et maintenons la somme des chiffres jusqu'à présent. Nous récurons ensuite la somme restante et le nombre de chiffres restants. Nous traitons les 0 principaux séparément car ils ne sont pas comptés comme des chiffres.
Vous trouverez ci-dessous une simple implémentation récursive de l’idée ci-dessus –
// A C++ recursive program to print all n-digit // numbers whose sum of digits equals to given sum #include
// 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 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# 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.
<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>
// 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 ?> Sortir:
12 21 30
Complexité temporelle : O(n*n!)
Espace auxiliaire : Sur)