{"id":626,"date":"2020-06-10T07:37:46","date_gmt":"2020-06-10T07:37:46","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=626"},"modified":"2022-03-25T10:20:19","modified_gmt":"2022-03-25T10:20:19","slug":"n-digit-sum","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/n-digit-sum\/","title":{"rendered":"N Digit Sum"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Recursion<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a digit N<\/code> and an integer Sum<\/code>, print all the N<\/code>-digit integers whose digit sum is equal to the given Sum<\/code>. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : N = 2, Sum = 8\n\nOutput : 17 26 35 44 53 62 71 80\n\nExplanation : All these elements are valid 2 digit integers with sum of digits as 8.\n<\/code><\/pre>\n
Can we use Recursion<\/code> here ?<\/em><\/strong><\/p>\n
\n
Of course, we need to find all combinations of N<\/code> digits that sum up to a given Sum<\/code>. Such combinations can be easily generated using Recursion<\/code>. <\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. The idea is to generate all N<\/code> digits numbers recursively and print numbers whose sum of digits is equal to given Sum<\/code>.  <\/li>\n
  2. Initialize an empty string str = ""<\/code>.<\/li>\n
  3. Recursively append digits  (0-9)<\/code> to str<\/code> and subtract digits from Sum<\/code> till the length of str<\/code> becomes N<\/code>.  <\/li>\n
  4. If length of str<\/code> becomes N<\/code> and Sum<\/code> becomes 0<\/code>, this implies that the stored number in str<\/code> is a valid number. Hence print str<\/code>.<\/li>\n<\/ol>\n<\/blockquote>\n
    NOTE<\/strong>: One important observation is, leading 0<\/code>‘s must be
    \nhandled explicitly as they are not counted as digits.<\/p>\n
    ALGORITHM:<\/h3>\n
    str = ""\n\nNdigitNums (str, n, sum)\n  if (length of str becomes n and sum becomes 0)\n    print str\n\n  Run loop from d = '0' to '9'\n     NdigitNums (str+d, n-1, sum-d)\n<\/code><\/pre>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t