1. ## Combinations Algorithm

I'm looking for an efficient algorithm to take a set $\displaystyle S=\{s_1,\ldots,s_n\}$ and return all possible subsets (minus $\displaystyle \emptyset$), where order doesn't matter.

Example: Given $\displaystyle S=\{1,2,3\}$, the output would be $\displaystyle \{1,2,3\},\;\{1,2\},\;\{1,3\},\;\{2,3\},\;\{1\},\; \{2\},\;\{3\}$.

-Thanks!

2. Originally Posted by chiph588@
I'm looking for an efficient algorithm to take a set $\displaystyle S=\{s_1,\ldots,s_n\}$ and return all possible subsets (minus $\displaystyle \emptyset$), where order doesn't matter.

Example: Given $\displaystyle S=\{1,2,3\}$, the output would be $\displaystyle \{1,2,3\},\;\{1,2\},\;\{1,3\},\;\{2,3\},\;\{1\},\; \{2\},\;\{3\}$.

-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) {
return;
}
ArrayList<Integer> option1 = new ArrayList<Integer>(list);
getSubsets(x+1, option1);
ArrayList<Integer> option2 = new ArrayList<Integer>(list);
}
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}