주어진 자릿수 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
Java의 csv 파일에서 읽기
에이 간단한 해결책 모든 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
시간 복잡도: 오(안*안!)
보조 공간: 에)