Break the string of numbers into groups of 1 digit and 2 digit numbers

Question

I am trying to break a given string of numbers into smaller 1 digit and 2 digit numbers. Something like this:

Input : 1234 Output : (1,2,34) (1,23,4) (1,2,3,4) (12,34) (12,3,4)

I have been trying to use backtracking to solve the problem, but haven't been able to get the perfect result. My attempt is as follows:

import java.util.Arrays;
import java.util.ArrayList;

public class MyClass {

    private static void func(ArrayList<String> res, String digits, String s){
        if(digits.length() <= 0){
            res.add(s.substring(0, s.length()-1));
            return;
        }

        String temp = digits;
        String prev_s = s;

        s = s  + digits.charAt(0) + ","; // chosen one character
        func(res, digits.substring(1), s);

        prev_s = s;

        if(digits.length() >= 2){
            s = s +  digits.substring(0,2) + ","; // chosen two characters
            func(res, digits.substring(2), s);
        }

        s = prev_s;
        digits = temp; // unchoosing
    }

    public static void main(String args[]) {

        String digits = "1234";
        ArrayList<String> res = new ArrayList<>();
        String s = "";
        func(res, digits, s);
        for(int i =0; i < res.size(); i++){
            System.out.println(res.get(i));
        }
    }       
}

The answer that I get is as follows:

1,2,3,4
1,2,3,34
1,2,23,4
1,12,3,4
1,12,3,34

What wrong am I doing? I think I am messing up somewhere while creating the substring.

Also, can this problem be solved without using Backtracking? Thanks!

Answer 1

Your problem is the assignment to restore s is the wrong way:

prev_s = s; → s = prev_s;

That alone will fix your problem.

---

Beyond that:

• You don't need the last two statements. They don't do anything.
  Remember, Java is pass-by-value, so you don't need to restore parameters before returning.

• You shouldn't change the values of parameters. Instead, just do the concatenation in the recursive method call.

• Remove temp and prev_s since they are no longer needed.

• Code can be slightly simplified by prefixing the comma, instead of suffixing it.

public class MyClass {
    private static void func(ArrayList<String> res, String digits, String s){
        if (digits.isEmpty()) {
            res.add(s.substring(1));
            return;
        }
        func(res, digits.substring(1), s + ',' + digits.charAt(0));
        if (digits.length() >= 2) {
            func(res, digits.substring(2), s + ',' + digits.substring(0, 2));
        }
    }

    public static void main(String args[]) {
        ArrayList<String> res = new ArrayList<>();
        func(res, "1234", "");
        for (String r : res) {
            System.out.println(r);
        }
    }
}

Output

1,2,3,4
1,2,34
1,23,4
12,3,4
12,34