[prev] 87 [next]

Example: Subset Sum (cont)

Given: a set of n distinct integers in an array A …
  • produce all subsets of these integers
A method to generate subsets:
  • represent sets as n bits   (e.g. n=4, 0000, 0011, 1111 etc.)
  • bit i represents the i th input number
  • if bit i is set to 1, then A[i] is in the subset
  • if bit i is set to 0, then A[i] is not in the subset
  • e.g. if A[]=={1,2,3,5} then 0011 represents {1,2}