Monday, December 5, 2011

Generate all the subsets of a given set

This could be tricky unless you realize that given an set of size n there are 2^n subsets. An element can be in or out, so 0/1 and this means that you just need to generate all the binary numbers from 0  to n. The binary representation of each number will tell you whether or not you need to include the element (bit i = 1 means element in).
Pubblicato da a

4 comments:

  1. NoNameDecember 12, 2011 at 1:23 PM

    T[] arr = ...;
    var subsets = from m in Enumerable.Range(0, 1 << arr.Length) select from i in Enumerable.Range(0, arr.Length) where (m & (1 << i)) != 0 select arr[i];

    ReplyDelete
  2. NoNameDecember 12, 2011 at 1:24 PM

    This comment has been removed by the author.

    ReplyDelete
  3. UnknownJanuary 16, 2012 at 8:27 AM

    My solution using backtracking

    http://www.geeksforgeeks.org/archives/14469

    ReplyDelete
  4. codingplaygroundJanuary 25, 2012 at 10:36 PM

    There is another one which is better and simpler

    ReplyDelete

Subscribe to: Post Comments (Atom)