# Subsets

## Each element is either in the subset or not

`*`

: element is in subset`-`

: element NOT in subset

so subsets of `[1,2,3]`

are

```
[-,-,*] = [3]
[*,-,-] = [1]
[-,*,-] = [2]
[*,*,*] = [1,2,3]
[*,-,*] = [1,3]
[-,*,*] = [2,3]
[*,*,-] = [1,2]
[-,-,-] = []
```

some brute force codes may look like a DFS

```
search(pos)
if found
output
for state in IN, NOT_IN
if IN
subset[pos] = current element
else
subset[pos] = nothing
search(pos + 1)
```

## Binary

use binary to repsent only two states

```
001 = [3]
100 = [1]
010 = [2]
111 = [1,2,3]
101 = [1,3]
011 = [2,3]
110 = [1,2]
000 = []
```

binary => decimal (000 .. 111 => 0 .. 7)

```
for i 0 .. 2^n - 1
b = convert i to binary
subset = select elements using b
yield subset
```

### Source code *Read on Github*

```
1 public class Solution {
2 public List<List<Integer>> subsets(int[] S) {
3 Arrays.sort(S);
4
5 return IntStream.range(0, 1 << S.length)
6 .mapToObj(mask ->
7 IntStream.range(0, S.length)
8 .filter(i -> ((1 << i) & mask) > 0)
9 .map(i -> S[i])
10 .boxed()
11 .collect(Collectors.toList())
12 )
13 .collect(Collectors.toList());
14 }
15 }
```