# Algorithm to extract combinations of array

I’m stuck with the problem to find possible combinations in an array. Currently, i solving this problem using Java Programming language. Here is the example:

```String[] array = new String[]{"AAA", "BBB", "CCC", "DDD"};
```

And here is the output that i want, so i can solve the fundamental issues:

```//possibility number 1
["AAA"],["BBB"],["CCC"],["DDD"]
//possibility number 2
["AAA","BBB"],["CCC"],["DDD"]
//possibility number 3
["AAA","BBB","CCC"],["DDD"]
//possibility number 4
["AAA"],["BBB","CCC"],["DDD"]
//possibility number 5
["AAA"],["BBB"],["CCC","DDD"]
//possibility number 6
["AAA"],["BBB","CCC","DDD"]
//etc.
```

The purpose is to generate combinations with sorted conditions as pairs of array like that. How to solve this? I need the algorithm, if can provide some example in another programming language its still very helpful!!

The most natural way is using recursion where you assume output is empty

```[
]
```

then you add a new list with one group with one element

```[[[A]]
]
```

then for every previous group simply add on every position or at the end

```[[[A,B]]
,[[A],[B]]
]
```

and (more simple than @kcsquared link) you can write

```static <T> List<List<List<T>>> partitions(List<T> set) {
// current element
T element = set.get(0);

if(set.size() == 1)
return singletonList(singletonList(singletonList(element)));

List<List<List<T>>> current = new ArrayList<>();

for (List<List<T>> p : partitions(set.subList(1, set.size()))) {
// every candidate group to place
for(int i = 0; i < p.size(); i++) {
List<List<T>> b = new ArrayList<>(p);
}
List<List<T>> b = new ArrayList<>(p);
}

return current;
}
```

if you run

```for (List<List<String>> x : partitions(List.of("AAA", "BBB", "CCC", "DDD")))
System.out.println(x);
```

you get

```[[DDD, CCC, BBB, AAA]]
[[DDD, CCC, BBB], [AAA]]
[[DDD, CCC, AAA], [BBB]]
[[DDD, CCC], [BBB, AAA]]
[[DDD, CCC], [BBB], [AAA]]
[[DDD, BBB, AAA], [CCC]]
[[DDD, BBB], [CCC, AAA]]
[[DDD, BBB], [CCC], [AAA]]
[[DDD, AAA], [CCC, BBB]]
[[DDD], [CCC, BBB, AAA]]
[[DDD], [CCC, BBB], [AAA]]
[[DDD, AAA], [CCC], [BBB]]
[[DDD], [CCC, AAA], [BBB]]
[[DDD], [CCC], [BBB, AAA]]
[[DDD], [CCC], [BBB], [AAA]]
```

(you can reverse input list or output list or any other order you wish)

E.g. change

```// last element
T element = set.get(set.size() - 1);
```

and

```...: partitions(set.subList(0, set.size() - 1))
```

to get

```[[AAA, BBB, CCC, DDD]]
[[AAA, BBB, CCC], [DDD]]
[[AAA, BBB, DDD], [CCC]]
[[AAA, BBB], [CCC, DDD]]
....
```