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 এর সাইজ)

	#include<bits/stdc++.h>
	using namespace std;
	unsigned long long dp[21][500001];
	unsigned long long f(int num_of_digit_left,int sum_left){
	if(num_of_digit_left==0){
	if(sum_left==0) return 1;
	return 0;
	}
	if(dp[num_of_digit_left][sum_left] !=-1) return dp[num_of_digit_left][sum_left];
	unsigned long long s = 0;
	for(int i=0;i<10;i++) if(sum_left-i>=0) s += f(num_of_digit_left-1,sum_left-i);
	return dp[num_of_digit_left][sum_left] = s;
	}
	unsigned long long ff(int num_of_digit,int sum){ ///for not having leading zero
	unsigned long long s = 0;
	for(int i=1;i<10;i++) if(sum-i>=0) s += f(num_of_digit-1,sum-i);
	return s;
	}
	int main(){
	int n,sum;
	memset(dp,-1,sizeof(dp));
	cin>>n>>sum;
	cout<<ff(n,sum)<<"\n";
	}

view raw n digit numbers with sum of digit as sum with no leading zero.cpp hosted with ❤ by GitHub