Find two distinct subsets of a list that add up to the same value This code should partition a list into two subsets of the given list that add up to the same number: for example [15, 5, 20, 10, 35, 25, 10] -&gt; [15, 5, 10, 15, 10], [20, 35] would be a valid solution. I'm looking for any tips to improve code style (be more Pythonic) or performance (mainly improvements to the algorithm used, but Python-specific things are also welcome). Thanks!

from collections import Counter


def partition_into_equal_parts(l):
    '''Partitions s into two subsets of l that have the same sum.

    &gt;&gt;&gt; problem = [15, 5, 20, 10, 35, 25, 10]
    &gt;&gt;&gt; first, second = partition_into_equal_parts(problem)
    &gt;&gt;&gt; valid_solution(first, second, problem)
    True
    '''
    total = sum(l)
    # If sum is odd, there is no way that total = sum(first) + sum(second) = 2 * sum(first)
    if total % 2:
        return
    first = subset_sum(total // 2, l)
    if first is None:
        return
    second = []
    # Fill second with items from counter
    second_counter = Counter(l) - Counter(first)
    for number, amount in second_counter.items():
        second.extend([number] * amount)
    return first, second


def valid_solution(first, second, problem):
    return sum(first) == sum(second) and Counter(first) + Counter(second) == Counter(problem)


def subset_sum(k, lst):
    '''Returns a subset of lst that has a sum of k.

    &gt;&gt;&gt; sum(subset_sum(24, [12, 1, 61, 5, 9, 2]))
    24
    &gt;&gt;&gt; subset_sum(53, [12, 13, 14])
    '''
    return recursive_calculate(k, sorted(lst, reverse=True), 0)


def recursive_calculate(k, lst, start):
    for idx in range(start, len(lst)):
        if lst[idx] == k:
            return [lst[idx]]
        elif lst[idx] &lt; k:
            rest = recursive_calculate(k - lst[idx], lst, idx + 1)
            if rest is not None:
                rest.append(lst[idx])
                return rest
Some "more pythonic" suggestions which also improve performance:


use Counter.elements()


in partition_into_equal_parts this code:

second = []
# Fill second with items from counter
second_counter = Counter(l) - Counter(first)
for number, amount in second_counter.items():
    second.extend([number] * amount)


can be merely replaced by

second = list((Counter(l) - Counter(first)).elements()


As Counter.elements returns a chained iterable of the expanded elements according to their count. So no need to do that with a loop and an extra list.


Cache the indexed element


In recursive_calculate, you have to use the index in

for idx in range(start, len(lst)):


but why not storing lst[idx] in a local variable? It's repeated a lot of times, and accessing a list element is costly. Just cache this access since you're not writing in lst (well you're writing to the end of it, recursively, but lst[idx] isn't udpated because the index is low enough).

def recursive_calculate(k, lst, start):
    for idx in range(start, len(lst)):
        element = lst[idx]
        if element == k:
            return [element]
        elif element &lt; k:
            rest = recursive_calculate(k - element, lst, idx + 1)
            if rest is not None:
                rest.append(element)
                return rest
    return None


Small note: python functions implicitly return None, but "Explicit is better than implicit" (The Zen Of Python) so it's better to actually return it.