CONCEPTS USED:
Recursion
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Given a digit
Nand an integerSum, print all theN-digit integers whose digit sum is equal to the givenSum.
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
Ndigits that sum up to a givenSum. Such combinations can be easily generated usingRecursion.
SOLVING APPROACH:
- The idea is to generate all
Ndigits numbers recursively and print numbers whose sum of digits is equal to givenSum.- Initialize an empty string
str = "".- Recursively append digits
(0-9)tostrand subtract digits fromSumtill the length ofstrbecomesN.- If length of
strbecomesNandSumbecomes0, this implies that the stored number instris a valid number. Hence printstr.
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.