Given n & sum find all the n digit numbers with sum of digit as sum with no leading zero

1 <= n <=20
1<= sum <= 500000

n টা ডিজিট এর প্রতিটায় ০ - ৯ ১ বার বসিয়ে আমরা মোট n^10 টা সংখ্যা generate করতে পারি। কিন্তু আমাদের বলা হয়েছে যে generate করা সংখ্যাটার প্রথম ডিজিট ০ হতে পারবে না। তাহলে আমরা প্রথম ডিজিটটাকে আলাদা ভাবে handle করব।

আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে n এর কত গুল ডিজিট বাকি আর আমার sum কত টুকু বাকি।

আমরা প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব।

BaseCase:

যদি num_of_digit_left যদি ০ হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।

যদি num_of_digit_left যদি ০ হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।

প্রথম ডিজিটটাকে আলাদা ভাবে handle:

যেহেতু প্রথম ডিজিট ০ হতে পারবে না তাই আমরা প্রথম ডিজিটটাতে ০ ছাড়া বাকি ৯ টা  সংখ্যার  সবগুলো সংখ্যা নিয়ে একবার  আগাবো।

dynamic programming:

আমরা যদি n = ৫ আর sum যে কোন সংখ্যা দিয়ে function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি। (20*500000 =  < 10^8 যা ম্যাক্সিমাম কোন  array এর সাইজ)