We can solve this with dynamic programming.
Given an array [a, b, c, d]
we start at:
r = [a]
adding b, we have
r = [a], [a, b], [b]
adding c, we have
r = [a], [b], [a, b], [a, b, c], [b, c], [c]
so the formula is:
Assuming after adding the i-1th element, the subarrays are r[i-1], then after adding the ith element, the subarrays will be:
r[i] = r[i-1], r[i-1] x a[i], a[i]
The following code realizes this algorithm. The time complexity is 2^N, where N is the original array's length.
public class AllSubSets {
public static void printAllSubSets(String str) {
if(str == null || str.length() < 1 ) {
return;
}
List<String> subarrays = new ArrayList<String>(); //Set won't work, need List
subarrays.add(str.substring(0, 1));
for(int i = 1; i < str.length(); i++) {
String addition = str.substring(i, i + 1);
int len = subarrays.size(); //take len outside the loop
for(int j = 0; j < len; j++) { //for(String s : subarrays) will throw concurrent exception
subarrays.add(subarrays.get(j) + addition);
}
subarrays.add(addition);
}
for(String s : subarrays) {
System.out.println(s);
}
}
public static void main(String[] args) {
String str = "abc";
printAllSubSets(str);
}
}
We can also solve this problem with a mask like subnet mask.
a b c d & 1 1 1 1 = a b c d
a b c d & 0 0 0 0 = ""
a b c d & 1 0 0 0 = a
We can get all the masks by starting from 0, keeps adding 1 until reach 1111.
