p103_is_special_sum_set

p103_is_special_sum_set.py

def is_special_sum_set(A):
    l = len(A)
    #Generate all subsets and categorize them by length of set
    #Then subsets[x] = all subsets of length x
    subsets = [[] for x in range(l + 1)]
    
    #Keep track of sums to test for duplicates (Condition 1)
    sums = []
    
    #Here we generate all subsets while checking if condition 1 is satisfied
    for x in range(pow(2, l)):
        #If a set has l elements then every subset can be represented as a binary string
        #For example if I have a set [a, b, c, d] then 1001 represents the subset [a, d]
        # 101 represents [a, c] etc. Therefore I loops from 0 to 2^l
        mask = bin(x)[2:] #binary form
        s = [A[i] for i, y in enumerate(reversed(mask)) if y == "1"] #Turn binary form into subset
        sum_s = sum(s) #Sum of the subset
        if sum_s in sums:
            #Test condition 1
            return False
        sums.append(sum_s)
        subsets[len(s)].append((s, sum_s))
    
    #Test condition 2
    #The idea is that we keep track of the maximum subset sum we have encountered up to length l
    #If we find that the minimum subset sum of subsets of a length greater than l is less than the current 
    #maximum subset sum, then Condition 2 has been violated
    max_sum = max([y for (_, y) in subsets[1]])
    for x in range(2, len(A) + 1):
        min_sum = min([y for (_, y) in subsets[x]])
        if min_sum < max_sum:
            #Test Condition 2
            return False
        max_sum = max([y for (_, y) in subsets[x]])
    return True