プラス記号を挿入するときに数字のすべての組み合わせを見つける

Question

私は練習アルゴリズムの質問を勉強していますが、この質問を解決できないようです。私は1234のような番号を与えています。私はそれに+シンボルを追加するときに番号の異なる組み合わせを見つける必要があります。答えには複数のプラス記号があります。結果は1+234、1+2+34、12+34などのようになります。私はどのように異なる部分文字列を見つけるのか分かりませんが、それらを追加する方法はわかりません。ここに私が持っているものは次のとおりです。

数字を文字列に変換すると、これはちょうど異なる部分文字列を保存します。正しい文字列を作成するにはどうすればこれらをまとめることができますか？私はプレフィックスで再帰を考えていましたが、その権利を得ることはできませんでした。

これは同じ順番で番号を保持するように求められているので、+を追加するので、これは順列問題とは異なります。

Answer 1

引数argのすべての可能な分割を生成したいとします。 引数argは、arg.length - 1ポイントに分割できます。 ここでは、ブール値の配列（divisors[N]）を使用して、文字arg[N]とarg[N + 1]の間で分割するかどうかを覚えています。 divisorsのすべての可能なバージョンが再帰的なフローの間に生成されます。最後に達したら、文字列の分割を行い、結果を保存します。

public static void cover(final String arg) { 
    final List<Set<String>> result = new ArrayList<>(); 

    final boolean[] divisors = new boolean[arg.length() - 1]; 
    processDivisors(divisors, 0, arg, result); 

    System.out.println(result); 
    // now the result contains the divisions, we can do something with it 
    doSomethingWithResult(result); 
} 

private static void processDivisors(final boolean[] divisors, 
            final int position, 
            final String arg, 
            /* out */ final List<Set<String>> result) { 

    if (position == arg.length() - 1) { 
     final Set<String> computedDivision = computeDivision(arg, divisors); 
     result.add(computedDivision); 
     return; 
    } 
    divisors[position] = true; 
    processDivisors(divisors, position + 1, arg, result); 
    divisors[position] = false; 
    processDivisors(divisors, position + 1, arg, result); 
} 

private static Set<String> computeDivision(final String arg, final boolean[] divisors) { 
    final Set<String> computedDivision = new TreeSet<>(); 
    int start = 0; 
    for (int i = 0; i < divisors.length; ++i) { 
     if (divisors[i]) { 
      computedDivision.add(arg.substring(start, i + 1)); 
      start = i + 1; 
     } 
    } 
    computedDivision.add(arg.substring(start, arg.length())); 
    return computedDivision; 
} 

private static void doSomethingWithResult(final List<Set<String>> result) { 
    for (final Set<String> coverage : result) { 
     final String message = String.join("+", coverage); 
     System.out.println(message); 
    } 
} 

このコードは完全ではないと強く信じています。何とか最適化できます。 Btw。除算を行うときに余分な操作を行う必要がある場合は、computeDivisonメソッドを変更することができます。しかし、その部分を印刷に使うことは絶対にありません。最初に出力を生成してから別のコードセグメントで処理する方が賢明でしょう。