[Python] Leetcode 78 Subsets

여러가지 방법이 있지만 bit masking 방식이 가장 좋았다.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        for i in range(0, 1<<len(nums)):
            temp = []
            for j in range(len(nums)):
                if i & 1<<j:
                    temp.append(nums[j])
            ret.append(temp)
        return ret

여기서 비트를 확인하면서 [0,0,0] 세 elements들에 대한 각 bit를 키꺼나 끄는 모든 조합을 확인하는 아이디어다.
shift를 이용하기 때문에 shift 0, 1, 2 이렇게 확인하면 비트는 거꾸로 올라가므로 001, 010, 100 (세 번 순회) 이렇게 가장 오른쪽에서부터 순회하며 확인한다.
가장 바깥에 있는 순회는 0부터 7까지 즉 000, ... , 111 까지의 모든 경우를 순회하는 것이고 여기서 각 비트가 어떻게 켜져 있는지를 안쪽 순회를 통해서 확인하여 비트가 켜져있는 index를 확인하여 elements에 담는 것이다.