A subset is a portion of a set. 
is a subset of 
(written 
)
iff every member of 
is a member of 
. If 
is a proper subset of 
(i.e., a subset other than the set itself), this is written
. If 
is not a subset of 
, this is written 
. (The notation 
is generally not used, since 
automatically means that 
and 
cannot be the same.)
The subsets (i.e., power set) of a given set can be found using Subsets[list].
An efficient algorithm for obtaining the next higher positive integer having the same number of 1 bits is given by Gosper (1972, p. 81) in PDP-10 assembler. When subsets are encoded by bit masks and the resulting mask fits in the chosen number of bit positions, this computes the next subset of the same cardinality in numerical bit-mask order.
The set of subsets of a set 
is called the power set of 
, and a set of 
elements has 
subsets (including both the set itself and the empty
set). For each 
,
1, ..., 
, the number of distinct k-subsets
on a set of 
elements is the binomial
coefficient 
.
Summing over all subset sizes gives the binomial sum
 |
For sets of 
,
2, ... elements, the numbers of subsets are therefore 2, 4, 8, 16, 32, 64, ... (OEIS
A000079). For example, the set 
has the two subsets 
and 
. Similarly, the set 
has subsets 
(the empty set), 
, 
, and 
.
