Efficient Generation of Subsets with a Given Sum
Dominique Roelants van Baronaigien,
Department of Computer Science,
University of Victoria, Canada.
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Let C(n,p) denote the set of all subsets of
{1,2,...,n} whose sum is p, and let
C(n,k,p) denote the
k element sets of
C(n,p). We show that the elements of
C(n,p) and
C(n,k,p)
can be generated efficiently by a simple
recursive algorithms. The subsets are represented
by characteristic bitstrings and by lists of elements.
These representations can be generated in time
that is proportional to the number of subsets generated.
-
The postscript file is 163,617 bytes,
the dvi file is 34,196 bytes.
-
Appeared in Journal of Combinatorial Mathematics and Combinatorial
Computing 14 (1993) 87-96.
Back to list of publications.