# for an array of int, find if there is a subset whose sum could divisible by M
# https://www.geeksforgeeks.org/subset-sum-divisible-m/
class Solution(object):
    def modularSum(self, arr, M):
        """
        :type arr: List[int]
        :type M: int
        :rtype: boolean
        """

        res = set()
        # test case [1,2,7],5, at begining we have res = set(), when comes to `1`, we have {1}
        # then comes 2, we could have {1} + {2} + {(1+2)%5} = {1,2,3}
        # then comes 7, we have {1,2,3} + {7} + {(1+7)%5, (2+7)%5, (3+7)%5} = {1,2,3, 4,0}
        for n in arr:
            res |= {n % M} | {(n + i) % M for i in res}

        print res
        return 0 in res


if __name__ == '__main__':
    print Solution().modularSum([1, 6], 5)
    print Solution().modularSum([1, 2, 7], 5)
    print Solution().modularSum([1, 3, 7], 5)
    print Solution().modularSum([1, 4, 7], 5)
    print Solution().modularSum([1, 5, 7, 6], 5)
