Python Fast One-Liner [Bit Manipulation] [List Comprehension] [Iterative]


  • 0
    J
    return [[nums[offset] for offset in range(inclusions.bit_length()) if inclusions&(1<<offset) != 0] for inclusions in range(1<<len(nums))]
    

    Here's the rundown:

    We're trying to generate the set of all subsets (aka power set) of a list.

    ... nums[offset] for offset in range(inclusions.bit_length()) ...
    

    To keep track of which elements are kept, inclusion is encoded as 1, exclusion as 0. The number of bits used is the size of the input. For 3 elements, it goes from 0 to 7 (111 in binary). For 16 elements, 0x0 to 0xFFFF.

    For example, if num = [1, 2, 3]:
    000 => []
    100 => [1]
    101 => [1, 3]
    111 => [1, 2, 3]

    ... if inclusions&(1<<offset) != 0 ...
    

    Bit masking checks if an element should be included or not.

    ... for inclusions in range(1<<len(nums)) ...
    

    For input of size N, there will be 2^N iterations, starting at 0, ending at 2^N-1.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.