给定位数n，打印所有n位数的数字，这些数字的总和等于给定的总和。解决方案不应考虑引导0作为数字。 例如：
null
Input: N = 2, Sum = 3Output: 12 21 30Input: N = 3, Sum = 6Output: 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 = 3Output: 1002 1011 1020 1101 1110 1200 2001 2010 2100 3000
A. 简单解决方案 将生成所有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 <bits/stdc++.h> 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. |
PHP
<?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 ?> |
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> |
输出：
12 21 30
时间复杂性： O（n*n！）
辅助空间： O（n）
本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
