Given a number N, we have to print the minimum subset of palindromes required to express N as a sum of them.
Examples :
Input : N = 11 Output : [ 11 ] Explanation : 11 is itself a palindrome. Input : N = 65 Output : [55, 9, 1] Explanation : 65 can be expressed as a sum of three palindromes (55, 9, 1).
Approach :
The problem can also be solved using largest palindrome number lesser than or equal to given number. In this approach we find the largest palindrome number lesser than or equal to given number and then subtract that number from the given number. And then again find the largest palindrome for the rest value left. This process goes until the rest value becomes equal to a single digit number.

Implementation :
#include <bits/stdc++.h>
using namespace std;
// A utility function to check if number is power of 10
bool Check(string s, int n)
{
if (s[0] == '1') {
for (int i = 1; i < n; i++) {
if (s[i] != '0')
return false;
}
return true;
}
return false;
}
// This function is to find the largest palindrome lesser
// than the number s
string generatePrevPalindrome(string s, int n)
{
// Input type 1: If number is power of 10
// simply o/p 9 n-1 times
if (Check(s, n)) {
string res;
for (int i = 1; i < n; i++)
res.push_back('9');
return res;
}
// For input type 2 and type 3
// find the index of mid digit
int mid = n / 2;
// A bool variable to check if copy of left side to
// right is sufficient or not
bool leftlarger = false;
// end of left side pointer is always 'mid -1'
int i = mid - 1;
// Beginning of right side pointer depends if n is odd
// or even
int j = (n % 2) ? mid + 1 : mid;
// Initially, ignoring the middle same digits
while (i >= 0 && s[i] == s[j])
i--, j++;
// If the string is palindrome itself
// then return the string
if (i < 0)
return s;
// Find if the middle digit(s) need to be decrmented or
// not (or copying left side is not sufficient)
if (s[i] > s[j]) {
// if leftlarger becomes true it means
// we need to decrement middle elements
leftlarger = true;
}
// Copy the mirror of left to right
while (i >= 0) {
s[j] = s[i];
j++;
i--;
}
// Handle the case where middle digit(s) must be
// decremented . This part of code is for CASE 1 and
// CASE 2.2
if (leftlarger == true) {
i = mid - 1;
int borrow = 1;
// If there are odd digits, then decrement
// the middle digit and store the borrow
if (n % 2 == 1) {
if (s[mid] == '0') {
// If middle element is zero ,then
// update the borrow value and middle digit
borrow = 1;
s[mid] = '9';
}
else {
borrow = 0;
s[mid] = s[mid] - 1;
}
j = mid + 1;
}
else {
j = mid;
}
// Subtract 1 to the rightmost digit of the left
// side, propagate the borrow towards MSB digit and
// simultaneously copying mirror of the left side to
// the right side.
while (i >= 0) {
if (borrow == 1) {
if (s[i] == '0') {
// If i th digit element is zero ,then
// update the borrow value and middle
// digit
borrow = 1;
s[i] = '9';
}
else {
borrow = 0;
s[i] = s[i] - 1;
}
}
// copy mirror to right
s[j++] = s[i--];
}
}
return s;
}
// Driver Program to test above function
int main()
{
// Given number
int num = 100;
vector<string> subset;
while (num >= 10) {
// Change the number into string format
string s = to_string(num);
// length of string
int n = s.length();
// Finding the largest palindrome lesser than given
// number
string pal = generatePrevPalindrome(s, n);
// storing in vector subset
subset.push_back(pal);
// Change the string into number format
int pal_num = stoi(pal);
// Process left for rest value
num = num - pal_num;
}
if (num != 0) {
subset.push_back(to_string(num));
}
for (int i = 0; i < subset.size(); i++) {
cout << subset[i] << " ";
}
return 0;
}
Time Complexity : O(n) where n is length of number