## Write a method that returns all subsets of a set

Write a method that returns all subsets of a set.

My initial thoughts:
Suppose we need to find the subsets of a set $A$ with size $k$, where $\left| A \right|=n$. We can scan every elements $a_{i}$ in $A$ and choose either to pick $a_{i}$ or not. If we pick $a_{i}$, we need to find another $k-1$ elements in the set $A - \{a_{i}\}$. If we do not choose $a_{i}$, we need to find another $k$ elements in the set $A - \{a_{i}\}$.
We can then find all subsets of $A$ by iterating $k$ through $0$ to $n$.

My initial codes:

	public static Set<Set<Character>> AllSubset
(Set<Character> elements) {
Set<Set<Character>> results =
new HashSet<Set<Character>>();

for (int i = 0; i <= elements.size(); ++i) {
Set<Set<Character>> temp =
new HashSet<Set<Character>>();
KSubsets(elements, new HashSet<Character>(),
temp, i);
}
return results;
}

public static void KSubsets(Set<Character> elements,
Set<Character> subset,
Set<Set<Character>> results, int k) {
if (k > elements.size())
return;
if (elements.size() == 0 || k == 0) {
Set<Character> putin = new HashSet<Character>();
for (Character o : subset)
subset = new HashSet<Character>();
return;
}
// include 1st element, choose k-1 element
// from the remaining n-1 elements
Character o = elements.iterator().next();
subset.add(o); // subset = {..., o}
Set<Character> newElements = new HashSet<Character>();
for (Character c : elements)
if (!c.equals(o))
KSubsets(newElements, subset, results, k - 1);

// exclude 1st element, choose k element
// from the remaining n-1 elements
subset.remove(o); // subset = {...}
newElements = new HashSet<Character>();
for (Character c : elements)
if (!c.equals(o))
KSubsets(newElements, subset, results, k);
}

Solution:

Recursion:
This is a great problem to implement with recursion since we can build all subsets of a set using all subsets of a smaller set. Specifically, given a set $S$, we can do the following recursively:

Let first = S[0]; Let smallerSet = S[1 ,…, n]
Compute all subsets of smallerSet and put them in allsubsets
For each subset in allsubsets, clone it and add first to the subset

ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> set,
int index) {
ArrayList<ArrayList<Integer>> allsubsets;
if (set.size() == index) {
allsubsets = new ArrayList<ArrayList<Integer>>();
} else {
allsubsets = getSubsets(set, index + 1);
int item = set.get(index);
ArrayList<ArrayList<Integer>> moresubsets =
new ArrayList<ArrayList<Integer>>();
for (ArrayList<Integer> subset : allsubsets) {
ArrayList<Integer> newsubset =
new ArrayList<Integer>();
}
}
return allsubsets;
}

Combinatorics:

When we’re generating a set, we have two choices for each element: (1) the element is in the set (the “yes” state) or (2) the element is not in the set (the “no” state). This means that each subset is a sequence of yesses/nos — e.g., “yes, yes, no, no, yes, no”.
This gives us $2^{n}$ possible subsets. How can we iterate through all possible sequences of “yes”/”no” states for all elements? If each “yes” can be treated as a 1 and each “no” can be treated as a 0, then each subset can be represented as a binary string.
Generating all subsets then really just comes down to generating all binary numbers (that is, all integers). Easy!

ArrayList<ArrayList<Integer>> getSubsets2(ArrayList<Integer> set) {
ArrayList<ArrayList<Integer>> allsubsets =
new ArrayList<ArrayList<Integer>>();
int max = 1 << set.size();
for (int i = 0; i < max; i++) {
ArrayList<Integer> subset = new ArrayList<Integer>();
int k = i;
int index = 0;
while (k > 0) {
if ((k & 1) > 0) {
}
k >>= 1;
index++;
}
}
return allsubsets;
}

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2de9e8d93d7', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2de9e8d9406',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2de9e8d9408',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});