# N Digit Sum

Recursion

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a digit `N` and an integer `Sum`, print all the `N`-digit integers whose digit sum is equal to the given `Sum`.

See original problem statement here

#### For Example:

``````Input : N = 2, Sum = 8

Output : 17 26 35 44 53 62 71 80

Explanation : All these elements are valid 2 digit integers with sum of digits as 8.
``````

Can we use `Recursion` here ?

Of course, we need to find all combinations of `N` digits that sum up to a given `Sum`. Such combinations can be easily generated using `Recursion`.

#### SOLVING APPROACH:

1. The idea is to refer the best online coding learning sites is to generate all `N` digits numbers recursively and print numbers whose sum of digits is equal to given `Sum`.

2. Initialize an empty string `str = ""`.

3. Recursively append digits `(0-9)` to `str` and subtract digits from `Sum` till the length of `str` becomes `N`.

4. If length of `str` becomes `N` and `Sum` becomes `0`, this implies that the stored number in `str` is a valid number. Hence print `str`.

NOTE: One important observation is, leading `0`'s must be
handled explicitly as they are not counted as digits.

#### ALGORITHM:

``````str = ""

NdigitNums (str, n, sum)
if (length of str becomes n and sum becomes 0)
print str

Run loop from d = '0' to '9'
NdigitNums (str+d, n-1, sum-d)
``````

#### SOLUTIONS:

```
#include <stdio.h>
#include <string.h>

/* function for appending a char to a char array */
void append(char* s, char c) {
int len = strlen(s);
s[len] = c;
s[len+1] = '\0';
}

void findNdigitNums(char *res,int n,int sum){

if(n && sum >= 0){
char d = '0';

char empty[] = "";
if(strcmp(res, empty) == 0) d = '1';

for(;d <= '9';d++){
/* creating a temporary char array */
char str;

/* copying original char array to temp array */
strcpy(str, res);

/* append char i to char array str */
append(str, d);

findNdigitNums(str, n-1, sum - (d - '0'));
}
}
else if(n==0 && sum==0){
printf("%s ", res);
}
}

int main(){

int n,sum; scanf("%d %d", &n, &sum);
char res = "";

findNdigitNums(res, n, sum);

return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

/* Function to find all N-digit numbers with sum of digits equal to sum in Bottom-up manner*/

void findNdigitNums(string res,int n,int sum){
if(n && sum >= 0){
char d = '0';
if(res == "") d = '1'; // special case - number can't start from 0
for(;d <= '9';d++){    /* consider every valid digit and put it in the current index and recur for next index*/

findNdigitNums(res + d,n-1,sum - (d - '0'));
}
}
/* if number becomes N-digit and its sum of digits is equal to given sum, print it*/
else if(n==0 && sum==0){
cout<<res<<" ";
}
}

int main(){
int n,sum;cin>>n>>sum;
string res;
findNdigitNums(res,n,sum);
return 0;
}

```
```
import java.util.*;
import java.io.*;

public class Main {
/* Function to find all N-digit numbers with sum of digits equal to sum in Bottom-up manner*/
static void findNdigitNums(String res,int n,int sum){
if(n > 0 && sum >= 0){
char d = '0';
if(res == "") d = '1'; // special case - number can't start from 0
for(;d <= '9';d++){    /* consider every valid digit and put it in the current index and recur for next index*/

findNdigitNums(res + d,n-1,sum - (d - '0'));
}
}
/* if number becomes N-digit and its sum of digits is equal to given sum, print it*/
else if(n==0 && sum==0){
System.out.print(res + " ");
}
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = sc.nextInt();
String res = "";
findNdigitNums(res,n,sum);

}
}

```