public static List decode(String encoded) {
List ans = new ArrayList();
 StringBuilder input1 = new StringBuilder();

    // append a string into StringBuilder input1
    input1.append(encoded);

    // reverse StringBuilder input1
    input1 = input1.reverse();

    // print reversed String
    //System.out.println(input1);
    encoded = input1.toString();

    int l = encoded.length();
    Map<Integer,List<String>> map = new HashMap<Integer,List<String>>();
    List<String> tList = new ArrayList<String>();
    tList.add("");
    map.put(l,tList);
    map.put(l+1,tList);

    for(int i=l-1; i>=0; i--) {
        List<String> currentList = new ArrayList<String>();

        if(i+2<=l) {
            String s1 = encoded.substring(i,i+2);
            if(isValid(s1)) {
                char c = (char)(Integer.parseInt(s1));
                List<String> t1 = map.get(i+2);
                for(String s:t1) {
                    String t = c+s;
                    currentList.add(t);
                }
            }
        }

        if(i+3<= l) {
            String s1 = encoded.substring(i,i+3);
            if(isValid(s1)) {
                char c = (char)(Integer.parseInt(s1));
                List<String> t1 = map.get(i+3);
                for(String s:t1) {
                    String t = c+s;
                    currentList.add(t);
                }
            }
        }
        map.put(i,currentList);

    }


    for(String s:map.get(0)) {
        System.out.println(s);
    }
    return map.get(0);

}

public static boolean isValid(String s) {
    int val = Integer.parseInt(s);
    return (val >=10 && val <=126);
}