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
Reazioni: 

4 commenti:

  1. 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. This comment has been removed by the author.

    ReplyDelete

  3. My solution using backtracking

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

    ReplyDelete

  4. There is another one which is better and simpler

    ReplyDelete

Subscribe to: Post Comments (Atom)