how to check Recursively if i can create a sum from a list of numbers? [closed]

by

To determine whether you can create a sum from a list or sublist of numbers:

1) Start with the first number.

2) If that number is equal to the sum you’re trying to create, stop, you’ve succeeded.

3) If that number is greater than the sum you’re trying to create, skip to the next number and go to step 2.

4) Subtract that number from the sum you’re trying to find.

5) Repeat this algorithm, trying to find the remaining sum with the remaining numbers (those after this one).

6) Go to the next number. If there is none, stop.

7) Go to step 2.

So, for example, if you’re trying to find a sum of 55 from [1, 13, 17, 8], you can reduce that to these three questions:

  1. Can you find a sum of 55-1 from [13, 17, 8]? (This will find any solutions that include the first number.)

  2. Can you find a sum of 55-13 from [17, 8]? (This will find any solutions that don’t include the first number but do include the second.)

  3. Can you find a sum of 55-17 from [8]? (This will find any solutions that don’t include the first or second number but do include the third.)

  4. Is 8 the solution? (This will find any solutions that don’t include the first three numbers but do include the fourth.)

Notice each new question has fewer terms than the original question. So it won’t go on forever.

More Related Contents:

  1. Python: maximum recursion depth exceeded while calling a Python object
  2. Why does this recursion return 0?
  3. One line recursive loop in python
  4. Removing duplicates in lists
  5. How to generate all permutations of a list?
  6. Recursive code returns None [duplicate]
  7. How to split text without spaces into list of words
  8. Finding a key recursively in a dictionary
  9. Understanding recursion in Python
  10. How can I build a recursive function in python? [duplicate]
  11. Find longest repetitive sequence in a string
  12. Python string ‘in’ operator implementation algorithm and time complexity
  13. Simple Python Challenge: Fastest Bitwise XOR on Data Buffers
  14. Algorithm to find which number in a list sum up to a certain number
  15. Checking if all elements in a list are unique
  16. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  17. Weighted random sample in python
  18. Python recursive function error: “maximum recursion depth exceeded” [duplicate]
  19. Can generators be recursive?
  20. What’s the algorithm of ‘set.intersection()’ in python?
  21. How to incrementally sample without replacement?
  22. Replace list of list with “condensed” list of list while maintaining order
  23. Is there a recursive version of the dict.get() built-in?
  24. Python Weighted Random [duplicate]
  25. How can I interleave or create unique permutations of two strings (without recursion)
  26. Python: powerset of a given set with generators [duplicate]
  27. getattr and setattr on nested subobjects / chained properties?
  28. What is this odd sorting algorithm?
  29. counting combinations and permutations efficiently
  30. Max recursion is not exactly what sys.getrecursionlimit() claims. How come?

Leave a Comment