Also, since the most straightforward way to recombine digits is via Long.valueOf(String), I am more confident leaving my digits as Characters as a reminder that we are going to come back to String.

Character.getNumericValue(char) might be even more straightforward (unfortunately I found it after completing my own solution).

I forgot to make my #getAllPossibleCombinations method return an unmodifiable hierarchy per the javadoc.