Find all combinations of a list of numbers with a given sum

by

You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn’t sum to 10:

import itertools

numbers = [1, 2, 3, 7, 7, 9, 10]
target = 10

result = [seq for i in range(len(numbers), 0, -1)
          for seq in itertools.combinations(numbers, i)
          if sum(seq) == target]

print(result)

Result:

[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]

Unfortunately this is something like O(2^N) complexity, so it isn’t suitable for input lists larger than, say, 20 elements.

More Related Contents:

  1. Subset sum Problem
  2. Mergesort with Python
  3. counting combinations and permutations efficiently
  4. Implement pow(x,n)%d with integers only. (without making use of library functions) [duplicate]
  5. Why does integer division yield a float instead of another integer?
  6. What do ellipsis […] mean in a list?
  7. Pinging servers in Python
  8. Reading file using relative path in python project
  9. Could not load dynamic library ‘cudart64_101.dll’ on tensorflow CPU-only installation
  10. python 3.2 UnicodeEncodeError: ‘charmap’ codec can’t encode character ‘\u2013’ in position 9629: character maps to
  11. Generate a random letter in Python
  12. Install opencv for Python 3.3
  13. PyQt4 to PyQt5 how?
  14. Python unpacking operator (*)
  15. Removing the TK icon on a Tkinter window
  16. Python 3.1.1 string to hex
  17. pandas or python equivalent of tidyr complete
  18. How do I run python 2 and 3 in windows 7? [duplicate]
  19. Self-reference or forward-reference of type annotations in Python [duplicate]
  20. ‘ModuleNotFoundError’ when trying to import module from imported package
  21. Is Python’s order of evaluation of function arguments and operands deterministic (+ where is it documented)?
  22. “For” loop first iteration
  23. How to make a command case insensitive in discord.py
  24. What does the slash mean when help() is listing method signatures?
  25. Appending to list in Python dictionary [duplicate]
  26. NumPy grouping using itertools.groupby performance
  27. A set union find algorithm
  28. Converting python string into bytes directly without eval()
  29. How do I resize buttons in pixels? (Tkinter)
  30. import httplib ImportError: No module named httplib

Leave a Comment