CONCEPTS USED:

Recursion

DIFFICULTY LEVEL:

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

  }
}


Previous post N Digit Sum Even Odd
Next post Multiplication of Digits

Leave a Reply

Your email address will not be published. Required fields are marked *