java - Find all the combination of substrings that add up to the given string -

i'm trying create data structure holds possible substring combinations add original string. example, if string "java" valid results "j", "ava", "ja", "v", "a", invalid result "ja", "a" or "a", "jav"

i had easy in finding possible substrings

    string string = "java";     list<string> substrings = new arraylist<>();     for( int c = 0 ; c < string.length() ; c++ )     {         for( int = 1 ; <= string.length() - c ; i++ )         {             string sub = string.substring(c, c+i);             substrings.add(sub);         }     }     system.out.println(substrings); 

and i'm trying construct structure holds valid substrings. not easy. i'm in mist of ugly code, fiddling around indexes, , no near of finishing, on wrong path completely. hints?

here's 1 approach:

static list<list<string>> substrings(string input) {      // base case: there's 1 way split single character     // string, , ["x"] x character.     if (input.length() == 1)         return collections.singletonlist(collections.singletonlist(input));      // hold result     list<list<string>> result = new arraylist<>();      // recurse (since tagged question recursion ;)     (list<string> subresult : substrings(input.substring(1))) {          // case: don't split         list<string> l2 = new arraylist<>(subresult);         l2.set(0, input.charat(0) + l2.get(0));         result.add(l2);          // case: split         list<string> l = new arraylist<>(subresult);         l.add(0, input.substring(0, 1));         result.add(l);     }      return result; } 

output:

[java] [j, ava] [ja, va] [j, a, va] [jav, a] [j, av, a] [ja, v, a] [j, a, v, a]