I am following Ahmed Aly's Ladder for Div2C problems and I am ... stuck on the first problem :(

489C

I have made a recursive solution very easily but it has timed out. I am thinking of somehow memoizing my solution but I am not sure how to do it.

I thought of memorizing using accumulated sum, but that gives wrong answers for many cases. I am not sure how to memoize from recursive. Here is my code for lowest number for example:

Map<Integer, String> memo = new HashMap<>();
public String lowest(int sum, String cur){
		if(sum > s || cur.length() > m) return "-1";
		if(sum == s && cur.length() == m) {
			map.put(sum, cur);
			return cur;
		}
		if(map.containsKey(sum)) return map.get(sum);

		for(int i = 0; i < 10; ++i){
			if(cur.isEmpty() && i == 0) continue;
			String next = lowest(sum + i, cur + String.valueOf(i));
			if(!next.equals("-1")){
				map.put(cur, next);
				return next;
			}
		}
		if(!map.containsKey(cur)) map.put(cur, "-1");
		return "-1";
	}

Without memo it works, but with it I am failing. Thanks very much