I am writing a program to count only the partitions of a number with distinct parts.I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained partition lists. I think my program runs correctly, as I have tested for some inputs and verified from OEIS. But it's extremely slow for n>15. I think my algorithm has a complexity currently north of O(n^3), but I couldn't think of a better way to do it. Can anyone help with making it faster?# Logic - The partition of a number 'n', will be 1 + the partition of 'n-1', 2 + the partition of 'n-2', and so on.# So we start from 1, and build partition lists based on previously gotten partitions# The loop doesn't have to go all the way till 1.# For example, for 6, we only have to go till 'n-3' and stop, because after that, we only get duplicate lists. This is not to say that we don't get# duplicates before, but after 'n-3', we get JUST duplicates# So we only have to go till n-x >= xfrom collections import Countercompare = lambda x, y: Counter(x) == Counter(y)def make_partitions(n):    # Bottom up approach starts at 1 and goes till n, building on partitions already obtained    # partitions dictionary contains list of lists of partitions    # Ex - 1: [[1]]    # Ex - 2: [[2], [1,1]]    # Ex - 3: [[3], [2,1], [1,1,1]]    partitions = {}    start = 1    while start <= n:        partitions[start] = []        # Appending the number itself as a partition of length 1        partitions[start].append([start])        # prev stores the number currently being used to build the partition list        prev = start - 1        # pp stores all partition lists obtained so far for the current number        pp = []        while prev >= start-prev:            # curr_partitions stores the partition lists that make up the desired number, FROM the current number            # Ex - for desired number 6, in first loop, it stores those lists which make up 6 from those of 5; in the second loop, from those of 4 and so on            curr_partitions = []            prev_partitions = partitions[prev]            for p in prev_partitions:                q = list(p)                q.append(start-prev)            # self-explanatory. compare function is used to see if the list already exists            does_exist_already = False            for ppp in pp:                if compare(q, ppp):                    does_exist_already = True            if not does_exist_already:                curr_partitions.append(q)        # We have got the entire list of partitions that make up the desired number FROM the current number, so we add to the dictionary        partitions[start].extend(curr_partitions)        prev -= 1        pp.extend(curr_partitions)    start += 1return partitionsdef answer(n):    partitions = make_partitions(n)    req_partition_list = partitions[n]    final_partition_list = []    count = 0    # This for loop is to weed out lists which contain duplicate values    for p in req_partition_list:        c = Counter(p)        if all(v==1 for v in c.values()):            final_partition_list.append(p)            count += 1    return countif __name__ == '__main__':    n = int(raw_input())    print answer(n)
High execution time on number partitioning program in Python 2.7
python;algorithm;time limit exceeded;complexity;dynamic programming