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] -> [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. >>> problem = [15, 5, 20, 10, 35, 25, 10] >>> first, second = partition_into_equal_parts(problem) >>> 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. >>> sum(subset_sum(24, [12, 1, 61, 5, 9, 2])) 24 >>> 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] < k: rest = recursive_calculate(k - lst[idx], lst, idx + 1) if rest is not None: rest.append(lst[idx]) return rest