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 }