Skip to content

Instantly share code, notes, and snippets.

@gjcourt

gjcourt/subset_sum.py

Created August 23, 2013 03:38
Show Gist options
  • Save gjcourt/6315303 to your computer and use it in GitHub Desktop.
Save gjcourt/6315303 to your computer and use it in GitHub Desktop.
Download ZIP
For a given sequence finds all solutions to the subset sum problem.
Raw
subset_sum.py
lst = [2, 2, 3, -5]
from itertools import *
[m[1] for m in zip(chain(*[combinations(lst, n) for n in range(1,len(lst)+1)]), chain(*[combinations(range(len(lst)), n) for n in range(1,len(lst)+1)])) if sum(m[0]) == 0]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment