leetcode

Subsets

Subsets

Slow Version

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n, res = len(nums), list()
        for i in xrange(2**n):
            res.append(filter(lambda x: x is not None, map(lambda x, y: y if (int(x) * y or y == 0 and int(x) != 0) else
 None, list(bin(i)[2:].zfill(n)), nums)))
        return res

BitwiseOperators Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        STDOUT = True
        for i in xrange(1 << len(nums)):
            if STDOUT: print 'i =', i
            tmp = []
            for j in xrange(len(nums)):
                if STDOUT: print '{0:03b}'.format(i), '&', '{0:03b}'.format(1 << j), '->', i & 1 << j
                if i & 1 << j:
                    if STDOUT: print 'pick', '{0:03b}'.format(1 << j), nums, 'j =', j, 'target', nums[j]
                    tmp.append(nums[j])
            if STDOUT: print 'i = {0:03b}'.format(i), 'tmp =', tmp
            res.append(tmp)
        return res

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
In [748]: s = Solution(); print s.subsets([1, 2, 3])
i = 0
000 & 001 -> 0
000 & 010 -> 0
000 & 100 -> 0
i = 000 tmp = []
i = 1
001 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
001 & 010 -> 0
001 & 100 -> 0
i = 001 tmp = [1]
i = 2
010 & 001 -> 0
010 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
010 & 100 -> 0
i = 010 tmp = [2]
i = 3
011 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
011 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
011 & 100 -> 0
i = 011 tmp = [1, 2]
i = 4
100 & 001 -> 0
100 & 010 -> 0
100 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 100 tmp = [3]
i = 5
101 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
101 & 010 -> 0
101 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 101 tmp = [1, 3]
i = 6
110 & 001 -> 0
110 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
110 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 110 tmp = [2, 3]
i = 7
111 & 001 -> 1
pick 001 [1, 2, 3] j = 0 target 1
111 & 010 -> 2
pick 010 [1, 2, 3] j = 1 target 2
111 & 100 -> 4
pick 100 [1, 2, 3] j = 2 target 3
i = 111 tmp = [1, 2, 3]
[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

leet code

https://wiki.python.org/moin/BitwiseOperators