All possible groups of combinations of array

After spending more hours than I'd like to admit on trying to figure out your algorithm and why it is slow, and after multiple false epiphanies, thinking that I have finally discovered the weakness in your program, I believe that, now, I have really found out where the problem with your code lies. Considering all the drafts I've written for explaining where your algorithms wastes performances, trying to format it so that it is easy to read, and even trying out some LaTeX expressions, the emphasis on the word "painfully" becomes all the more justified when I say that the explanation for your algorithm's unsatisfactory performance is really painfully simple. So here goes … the reason your code is slow is:

$$...$$
$$...$$
$$j$$
Seriously, when the for loop that introduces int j is executed after the first time, it does nothing it hasn't already done the first time around. All local variables declared outside the loop except result (i.e. the method parameters) have the exact same values as they did during the first execution of the loop. I can't believe I didn't see this earlier.

But now that I'm writing an answer to this question, I will also tell you what I did to make the code a bit more read-/understandable (in my opinion). Since, inside the method body, only elements from initialArray with an index larger than or equal to i are queried, and i doesn't serve any other purpose than to mark this index, I've eliminated i altogether and adjusted the recursive calls so that they only pass a sublist of the array with the relevant elements:

public Set<Set<Set<Integer>>> recurseGroups(List<Integer> integerList, List<Set<Integer>> currentGroups) {
    if (integerList.isEmpty()) {
        // ...
    }

    for (int j = 0; j < integerList.size(); ++j) {
        // ...
        Set<Integer> newGroup = new HashSet<>(Collections.singletonList(integerList.get(0)));
        currentGroups.add(newGroup);
        result.addAll(recurseGroups(integerList.subList(1, integerList.size()), currentGroups));
        currentGroups.remove(newGroup);

        // ...
        for (int k = 0; k < currentGroups.size(); ++k) {
            currentGroups.get(k).add(integerList.get(0));
            result.addAll(recurseGroups(integerList.subList(1, integerList.size()), currentGroups));
            currentGroups.get(k).remove(integerList.get(0));
        }
    }

    // ...
}

That way, no information that isn't needed enters the method, which makes it easier to understand its workings.

Also, the following line is really unnecessarily complicated:

Set<Integer> newGroup = new HashSet<>(Collections.singletonList(integerList.get(0)));

This creates a List that is never used again and serves no other purpose than to save one line of code. You might as well do this:

Set<Integer> newGroup = new HashSet<>();
newGroup.add(integerList.get(0));

Even with two lines, it still takes up less characters than the above version, and it doesn't do more than it needs to do, hence easier to read.

That's it, now I really have to go to sleep. Happy coding!

Thanks for sharing the code.

It really looks nice and clean but it focuses on handling of the data structure rather than on individual objects.

I'd look at this way:

I get unique groups if I only group with the values to the right:

 input [1,2,3,4]
 pick 1
 call pairing(1,[2,3,4]) -> [1,2][1,3][1,4]
 pick 2
 call pairing(2,[3,4]) -> [2,3][2,4] // but not [2,1]!

With this approach, would the result [[1,3,4],[2]] ever appear? – Simon Forsberg

Maybe we have to change the point of view. We usually look for constructive solutions, but maybe a destructive approach is more suitable:

 input [1,2,3,4]
 pick 1
 takeout( 1, [1,2,3,4])-> [1][2,3,4]
 pick 2
 takeout (2, [1,2,3,4]) -> [2][1,3,4]
 pick 1
   goup(1,[2,3,4])->
       takeout([1,2],[1,2,3,4])->[1,2][3,4]
       takeout([1,3],[1,2,3,4])->[1,3][2,4]
       takeout([1,4],[1,2,3,4])->[1,4][2,3]
       goup([1,2],[3,4])
          takeout([1,2,3],[1,2,3,4])-> [1,2,3][4]
 // ...

To avoid duplication of [1,2,3][4] and [4][1,2,3] we should stop the iteration at n/2...