Generate Self Descriptive Numbers

An integer is said to be self-descriptive if it has the property that, when digit positions are labeled 0 to N-1, the digit in each position is equal to the number of times that this digit appears in the number. Write a function that will generate all descriptive numbers with a maximum size of N.

Example 1:

Input: 2020
Output: true
Explanation:
Position 0 has value 2 and there are two 0s in the number
Position 1 has value 0 and there are no 1s in the number
Position 2 has value 2 and there are two 2s
Position 3 has value 0 and there are zero 3s

Example 2:

Input: 3211000
Output: true
Explanation:
Position 0 has value 3 and there are three 0s in the number
Position 1 has value 2 and there are two 1s in the number
Position 2 has value 1 and there is one 2 in the number
Position 3 has value 1 and there is one 3 in the number
Position 4 has value 0 and there are zero 4s
Position 5 has value 0 and there are zero 5s
Position 6 has value 0 and there are zero 6s

Let's first write a function that will check whether a given positive integer is self-descriptive.

bool validate(string n) {
        vector<char> freq(10);

        for(const char& c: n) {
                int v = c - '0';
                freq[v]++;
        }

        for(int i = 0; i < n.length(); i++) {
                int mtp = n[i] - '0';
                if(freq[i] != mtp)
                        return false;
        }

        return true;
}

A very important insight is since the values of each digit in the number are occurrences, its total digit number sum should equal to its length.

For example:

1210 -> 1 + 2 + 1 + 0 = 4,

21200 -> 2 + 1 + 2 +0 + 0 = 5

From this idea, we only need to check the numbers for which their digit number sum equal to its length.

The last insight is using recursion will make it easier to solve the problem. If we want to create a number of size K for example, we can go though all the possibilities for the first slot i:0 -> 9, and for every one of these possibilities, we can call the recursive function for a number of length of the original number minus 1, and a sum minus i.

The resulting strings will be on this form: i + result of(length -1, sum - i)

Solution

#include<bits/stdc++.h>

using namespace std;

bool validate(string n) {
        vector<char> freq(10);

        for(const char& c: n) {
                int v = c - '0';
                freq[v]++;
        }

        for(int i = 0; i < n.length(); i++) {
                int mtp = n[i] - '0';
                if(freq[i] != mtp)
                        return false;
        }

        return true;
}

vector<string> backtrack(int len, int t_sum) {
    vector<string> res;

    if(len == 1) // if we need just one more character, we put the remaining sum in it
        return {to_string(t_sum)};

    if(t_sum == 0) // if sum is 0 we add a buffer of zeroes to complete the appropriate size
        return {string(len, '0')};

    for(int i = 0; i <= t_sum; i++) { // choose number to put in the first slot
        for(const string& v: dfs(len - 1, t_sum - i)) // try to put t_sum-i(rest of t_sum) in a string of length l-1
        {
            res.push_back(to_string(i) + v);
        }
    }

    return res;
}

vector<string> generateSelfDescriptive(int max_len) {
    vector<string> res;

    for(int i = 4; i <= max_len; i++) { // smallest selfdescriptive number has a length of 4
        vector<string> tmp = backtrack(i, i);
        res.insert(res.end(), tmp.begin(), tmp.end());
    }

    return res;
}