java - 如何以所有可能的方式拆分一个数字？

Question

我有一个数字，假设是 123，我想生成一个包含所有可能的分割方式的列表列表:

[[1,2,3], [12,3], [1, 23], [123]]

我发现一段代码几乎可以做到这一点:http://www.quora.com/How-do-I-take-a-string-by-the-user-and-split-it-in-all-possible-ways 。

我稍微修改了一下:

class breakString 
{   
    public static List<List<Integer>> res = new ArrayList<>();

public static List<List<Integer>> breaker(String input, int start, int end, List ans)
{
    if(start > end)
    {
        System.out.println(ans);

        res.add(ans);
        System.out.println("res:" + res.toString());
    }
    else 
    {
            ans.add(input.charAt(start) + "");
            breaker(input, start+1, end, ans);

            int listSize = ans.size();
            ans.remove(listSize - 1);
            String lastChar = ans.get(listSize - 2).toString();
            ans.remove(listSize - 2);
            ans.add(lastChar + input.charAt(start) + "");
            breaker(input, start+1, end,ans);
    }
    return res;
}

public static void main(String args[])
{
String input = "123";

List ans = new ArrayList();
ans.add(input.charAt(0) + "");

breaker(input,1, input.length() - 1, ans);    
    System.out.println("----------------------------------------------");

    for (List<Integer> intList : res)
    {
        System.out.println(intList);
    }
}
}

但是虽然它打印了正确的解决方案，但我无法让它返回正确的结果。输出为:

[1, 2, 3]
res:[[1, 2, 3]]
[1, 23]
res:[[1, 23], [1, 23]]
[12, 3]
res:[[12, 3], [12, 3], [12, 3]]
[123]
res:[[123], [123], [123], [123]]
----------------------------------------------
[123]
[123]
[123]
[123]

您能否告诉我如何修复它以返回:

[[1,2,3], [12,3], [1, 23], [123]]

Answer 1

您可以考虑使用此解决方案，而不是使用回溯。假设输入是一个包含 n 位数字的数字。该数字可以在 n - 1 个位置拆分。我们可以将输入数字的每种分割方式描述为 boolean 值字符串，或者假设输入数字不大于 10^32 则为 int 字符串。现在问题非常简单:分割输入数字的每种不同方式都由 int 表示。 0 表示不拆分(将返回原始输入)，n - 1 最低有效位设置为 HI 的数字表示拆分为所有部分。现在开始实现:

public List<List<String>> split(int in) {
    List<List<String>> result = new ArrayList<>();

    String num = String.valueOf(in);

    //the maximum is to split the number at each possible position
    int maxSplit = 0;
    for (int i = 0; i < num.length() - 1; i++)
        maxSplit |= (1 << i);

    for (int i = 0; i <= maxSplit; i++) {
        List<Integer> split = new ArrayList<>();

        //translate the representation of the splitting into the respective indices
        for (int b = 0; b < num.length() - 1; b++)
            if ((i & (1 << b)) != 0)
                split.add(b + 1);

        //ensure that the last part of the solution is in the result
        split.add(num.length());

        //split the input in the specified way
        List<String> strings = new ArrayList<>();
        int lastSplit = 0;
        for (int s : split) {
            strings.add(num.substring(lastSplit, s));

            lastSplit = s;
        }

        result.add(strings);
    }

    return result;
}