Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# N Digit Sum

Last Updated on March 25, 2022 by Ria Pathak

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 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[10];

/* 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[10] = "";

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);

}
}
```
```def findNdigitNums(res, n, sum):

if(n and sum >= 0):

for d in range(10):

if(res == ""):

if d == 0:
continue

findNdigitNums(res + str(d), n - 1, sum - d)

elif(n == 0 and sum == 0):
print(res, end = " ")

n, sum = map(int, input().split())
res = ""
findNdigitNums(res, n, sum)
```

[forminator_quiz id="719"]

This article tried to discuss Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.