All possible groups of combinations of array Let's assume I have a one-dimensional array of integers of size n. My problem is to generate all the combination of all possible groups of size 1 to n, such as each combination has exactly one occurrence of each element. The order does not count:

[[1,2]] == [[2,1]]
[[1],[2]] == [[2],[1]]
[[1,2],[3,4]] == [[2,1],[4,3]] == [[4,3],[2,1]]...


For example, for the input array [1,2], I would get:

[[1,2]]
[[1],[2]]


With [1,2,3], I would have:

[[1,2,3]]
[[1,2],[3]]
[[1,3],[2]]
[[2,3],[1]]
[[1],[2],[3]]


And with [1,2,3,4]:

[[1,2,3,4]]
[[1,2,3],[4]]
[[1,2,4],[3]]
[[1,3,4],[2]]
[[2,3,4],[1]]
[[1,2],[3,4]] &lt;= Equivalent to [[3,4],[1,2]]
[[1,3],[2,4]] &lt;= Equivalent to [[2,4],[1,3]]
[[1,4],[2,3]] &lt;= Equivalent to [[2,3],[1,4]]
[[1,2],[3],[4]]
[[1,3],[2],[4]]
[[1,4],[2],[3]]
[[2,3],[1],[4]]
[[2,4],[1],[3]]
[[3,4],[1],[2]]
[[1],[2],[3],[4]]




My code below is working but is actually very slow when the list has more than 6 elements:

public Set&lt;Set&lt;Set&lt;Integer&gt;&gt;&gt; recurseGroups(List&lt;Integer&gt; initialArray, List&lt;Set&lt;Integer&gt;&gt; currentGroups, int i) {
    if (i == initialArray.size()) {
        // Deep copy current group to save its content
        Set&lt;Set&lt;Integer&gt;&gt; copy = currentGroups.stream()
                .map(HashSet::new)
                .collect(Collectors.toSet());

        return Collections.singleton(copy);
    }

    Set&lt;Set&lt;Set&lt;Integer&gt;&gt;&gt; result = new HashSet&lt;&gt;();

    for (int j = i; j &lt; initialArray.size(); ++j) {
        // Add a singleton group with the i-th integer
        // And generate groups with the remaining elements
        Set&lt;Integer&gt; newGroup = new HashSet&lt;&gt;(Collections.singletonList(initialArray.get(i)));
        currentGroups.add(newGroup);
        result.addAll(recurseGroups(initialArray, currentGroups, i + 1));
        currentGroups.remove(newGroup);

        // Add the i-th integer to each previous existing groups
        // And generate groups with the remaining elements
        for (int k = 0; k &lt; currentGroups.size(); ++k) {
            currentGroups.get(k).add(initialArray.get(i));
            result.addAll(recurseGroups(initialArray, currentGroups, i + 1));
            currentGroups.get(k).remove(initialArray.get(i));
        }
    }

    return result;
}

// Calling line
Set&lt;Set&lt;Set&lt;Integer&gt;&gt;&gt; groups = recurseGroups(Arrays.asList(1,2,3), new ArrayList&lt;&gt;(), 0)


By adding a log in the stop condition, I noticed the code actually adds many times the same group combinations. I suspect it would be possible to improve the stop condition or the loop, but I don't see how.
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&lt;Set&lt;Set&lt;Integer&gt;&gt;&gt; recurseGroups(List&lt;Integer&gt; integerList, List&lt;Set&lt;Integer&gt;&gt; currentGroups) {
    if (integerList.isEmpty()) {
        // ...
    }

    for (int j = 0; j &lt; integerList.size(); ++j) {
        // ...
        Set&lt;Integer&gt; newGroup = new HashSet&lt;&gt;(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 &lt; 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&lt;Integer&gt; newGroup = new HashSet&lt;&gt;(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&lt;Integer&gt; newGroup = new HashSet&lt;&gt;();
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!