Find all combinations of a number when inserting a plus sign

Question

I am studying practice algorithm questions and can not seem to solve this question. I am giving a number such as 1234. I need to find the different combinations of the number when adding a + symbol into it. There can be multiple plus symbols in the answer. So results would look like 1+234,1+2+34,12+34 etc. I know how to find the different substrings but not how to add them up. Here is what I have:

public static void findCombos(String string){
    List<String> substrings = new ArrayList<>();
    for( int i = 0 ; i < string.length() ; i++ )
    {
        for( int j = 1 ; j <= string.length() - i ; j++ )
        {
            String sub = string.substring(i, i+j);
            substrings.add(sub);
        }
    }
    System.out.println(substrings);
}

This just stores the different substrings if convert the number to a string. How would I put these together to create the correct string. I was thinking recursion with prefixes but could not get that right.

This is different than the permutation question because I am asked to keep the number in the same order but add +'s to it.

Possible duplicate of [Generating all permutations of a given string](https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string) — bgfvdu3w, Oct 02 '17 at 04:42

Adam Kotwasinski · Answer 1 · 2017-10-02T05:20:13.397

You want to generate all possible divisions of argument arg. The argument arg can be split in arg.length - 1 points. Here I am using a boolean array (divisors[N]) to remember whether you want to split between characters arg[N] and arg[N + 1]). All possible versions of divisors array are generated during the recursive flow - when you have reached the end, you then do the string division, and save the result.

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);
    }
}

I strongly believe this code is not perfect, and could be somehow optimized. Btw. if you need to do any extra operation when you do the division, you can modify the computeDivison method. But certainly wouldn't use that part for printing - it would be wiser to have the output generated first, and then processed in a different segment of code.

@user081608 Iterate over the list of sets `result` in `cover()` and use `System.out.println(String.join("+", set));`. — bgfvdu3w, Oct 02 '17 at 05:18
@user081608 see updated answer, basically what Mark had said — Adam Kotwasinski, Oct 02 '17 at 05:20
Is this type of string division a common computer science principle? I am struggling to follow the recursion here to see where they all come together and wanted to do some more research. — user081608, Oct 02 '17 at 05:24
String division not really, but recursion, and how it can be used to certain kind of problems certainly is. Here we are storing a partially computed solution (`divisors`) and do the real work only when we have reached the end (of string, in our case). You see similar solutions when working with graphs, for example. To better understand how it works you can add `System.out.println(Arrays.toString(divisors))` in `computeDivision`, then it should be easier to see how it works. — Adam Kotwasinski, Oct 02 '17 at 05:28

Find all combinations of a number when inserting a plus sign

1 Answers1