Well, turns out this kata is now a duplicate of https://www.codewars.com/kata/647d08a2c736e3777c9ae1db (integer partition with an upper limit) with a slight difference (subtracted a specific value from the end result).

Related to the issue below: The author didn't actually write a solution that can pass any input in the given range in time, and in fact, for the current input range the kata is impossible to be solved in time, since the complexity is at least O(n * w * h).

The tests are very weak: all random tests have at most w = 10, fixed tests go as much as w = 16, and all tests with bigger w is always full so a trivial solution exists.

I thought it was pretty easy as well, and I did C#

Though I suppose it's up to the mods. They've been on this site longer, they're probably better at gauging difficulty than we are

Yes, it's DP (left or right), and cache can speed it up.

Isn't this too easy to a 5kyu, or it's just easy for golang ?

This one is good, at first I thought my solution would time out, but actually it passed, which means O(n^2) for worst time complexity, can actually reach O(n * k) for the random batch test, where k is the average lengh of max Palindromic Substring from the test.

This basically gives the answer ...

Is this related to GCD and Extended Euclidean Algorithm ?

I think saying [0, 3, 6, 9] is chosen a bit misleading, as it looks like the answer will depend on the choice taken (but really it doesn't matter). I think it's better to remove the notion of choice of digits altogether, like the usual combinatorial katas.

You need to choose n digits first, as the example shows, and build only from these chosen digits.
I've updated the final sentence to emphasize that.

Anyway let me add it.

I thought that's part of integer definition, except 0 itself, but other rules (end with 9) excluded that.

Fixed .. didn't create kata for a while, forget how it worked ..

Missing requirement: a integer of length m should not start with 0.