Dada la cantidad de dígitos n, imprime todos los números de n dígitos cuya suma de dígitos se suma a la suma dada. La solución no debe considerar los 0 iniciales como dígitos.
Ejemplos:
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
Una solución simple sería generar todos los números de N dígitos e imprimir números que tengan la suma de sus dígitos igual a la suma dada. La complejidad de esta solución sería exponencial.
Una mejor solución es generar solo aquellos números de N dígitos que satisfagan las restricciones dadas. La idea es usar la recursividad. Básicamente, llenamos todos los dígitos del 0 al 9 en la posición actual y mantenemos la suma de los dígitos hasta el momento. Luego recurrimos para la suma restante y el número de dígitos restantes. Manejamos los 0 iniciales por separado, ya que no se cuentan como dígitos.
A continuación se muestra una implementación recursiva simple de la idea anterior:
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] = '\0';
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] = '\0' ;
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] = "\0"
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] = '\0';
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] = '\0';
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>
Producción:
12 21 30
Complejidad del tiempo: O(n*n!)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA