"""
This program calculates smallest subset of  {0, 1,...,n} such that for any element in [n] we can find 2 distinct elements that add to it
"""
import math

def check(Set, desired_val): #check if a Set of values can be pairwise added to hit all the elements in desired_val
    copy = set()
    for i in desired_val:
        copy.add(i)
        
    for i in range(len(Set)):
        if(2*Set[i] > len(desired_val)):
            break
        for j in range(i, len(Set)):
            if(Set[i] + Set[j] > len(desired_val)):
                break
            copy.discard(Set[i] + Set[j])
            if(len(copy)==0):
                return True
    return False


def optimize(available_val, desired_val, Set, max_num, final_set): #iterates through via backtracking all the possible Sets (subsets of available_val) of size max_num 
    if (len(Set) == max_num):
        if(check(Set, desired_val) and len(final_set)== 0):
            for i in Set:
                final_set.append(i) #final_set is the first found desired set
    else:
        for i in range(len(available_val)):
            if(len(final_set) > 0): #if final_set is found, break out of loop
                break
            Set.append(available_val[i])
            optimize(available_val[i+1:], desired_val, Set, max_num, final_set)
            Set.pop()

def minimize(available_val, desired_val): #finds minimal length of desired subset starting with considering max_num at 1 and going up until a desired subset is found
    final_set = []
    n = len(available_val)
    i = math.ceil(((1+8*n)**.5-1)/2)
    while(len(final_set)==0):
        optimize(available_val, desired_val, [], i, final_set)
        i=i+1
    return final_set

def count_minimum_helper(available_val, desired_val, Set, max_num, final_count): #Number of sets S of size A066063(n) such that {1, 2, ..., n} is a subset of S + S
    if (len(Set) == max_num):
        if(check(Set, desired_val)):
            final_count.append(0)
    else:
        for i in range(len(available_val)):
            Set.append(available_val[i])
            count_minimum_helper(available_val[i+1:], desired_val, Set, max_num, final_count)
            Set.pop()

def count_minimum(n): #Number of sets S of size A066063(n) such that {1, 2, ..., n} is a subset of S + S
    available_val = list(range(n+1))
    desired_val = list(range(1, n+1))
    final_set = []
    i = len(minimize(available_val, desired_val))
    count_minimum_helper(available_val, desired_val, [], i, final_set)
    return len(final_set)  


#run count_minimum to get the number of sets S of size A066063(n) such that {1, 2, ..., n} is a subset of S + S
#Example for n = 3:
print(count_minimum(3))