指定された桁数 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
ランダムSQLで並べ替える
あ 簡単な解決策 N 桁の数値をすべて生成し、その桁の合計が指定された合計と等しい数値を出力することになります。このソリューションの複雑さは指数関数的に増加します。
より良い解決策 指定された制約を満たす N 桁の数値のみを生成することです。アイデアは再帰を使用することです。基本的に、0 から 9 までのすべての数字を現在の位置に埋め、これまでの数字の合計を維持します。次に、残りの合計と残りの桁数を再帰的に求めます。先頭の 0 は数字としてカウントされないため、個別に処理します。
以下は、上記のアイデアの単純な再帰実装です。
// 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 ?> 出力：
12 21 30
時間計算量: お(ん*ん!)
補助スペース: の上）