Originally Posted by
chiph588@ I'm looking for an efficient algorithm to take a set
and return all possible subsets (minus
), where order doesn't matter.
Example: Given
, the output would be
.
-Thanks!
The first thing that comes to mind is recursion, in particular depth first search. Are you working in a specific programming language? The basic idea is to start with an empty list and then for each element recusively do: add the element to the list, or don't.
Looks like this in java
Code:
import java.util.ArrayList;
public class Subsets {
static ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
static int[] S = {1,2,3};
public static void main(String[] args) {
getSubsets(0, new ArrayList<Integer>());
System.out.println(subsets);
}
static void getSubsets(int x, ArrayList<Integer> list) {
if (x==S.length) {
if (!list.isEmpty()) subsets.add(list);
return;
}
ArrayList<Integer> option1 = new ArrayList<Integer>(list);
getSubsets(x+1, option1);
ArrayList<Integer> option2 = new ArrayList<Integer>(list);
option2.add(S[x]);
getSubsets(x+1, option2);
}
}