a function that return all possible sub arrays that sum up to a specific given number (need not to be a continuous sub array)

Question

I'm stuck with this problem when I was doing some math and I need to find all possible sums of a given number. Here is a sample input and output for a better understanding of the problem. Let say we are given an array arr=[1,2,3,4,5] and given number number=10 then i need something like this,

def solution(arr,number):
    #you can code here

output : [1,2,3,4],[2,3,5],[1,5,4],[1,3,6],[1,6]

Welcome to SO. This isn't a discussion forum or tutorial. Please take the [tour] and take the time to read [ask] and the other links found on that page. Invest some time with [the Tutorial](https://docs.python.org/3/tutorial/index.html) practicing the examples. It will give you an idea of the tools Python offers to help you solve your problem. — wwii, Jun 22 '20 at 02:40
1) Number 6 is not in arr, so why is there `[1, 3, 6] and [1, 6]`? And 2) `[1, 6]` sums to 7 not 10, so another reason not to include it. — DarrylG, Jun 22 '20 at 09:17
Yeah, I mistakenly forgot to add 6 in the last of the array and there had to four written instead of 1. — kush, Jun 22 '20 at 09:30

score 1 · Answer 1 · answered Jun 22 '20 at 03:00

1

There are many interesting answers and discussion here and also here.

Here is a quick (tested) answer for you:

import itertools

def solution(arr, number):
    for i in range(len(arr)+1):
        for s in list(itertools.combinations(arr, i)):
            if sum(s) == number:
                yield list(s)


arr = [ 1, 2, 3, 4, 5 ]
number = 10

print(list(solution(arr, number)))

Prints:

[[1, 4, 5], [2, 3, 5], [1, 2, 3, 4]]

answered Jun 22 '20 at 03:00

Rusty Widebottom

985
2
5
14

Well that is fine but this does not give all the arrays. [1,3,6] and [4,6] is not printed. – kush Jun 22 '20 at 03:52
You just need to add the 6 to the array. It was not included in your original question so I left it out. Try it! – Rusty Widebottom Jun 22 '20 at 04:02

score 1 · Answer 2 · answered Jun 22 '20 at 03:53

Solve using Dynamic Programming algorithm

def solve(arr, s, i = None, path = None, solutions = None):
  """Use Dynamic Programming to find subsequence of arr
     that sum to s
     
     Arguments:
         arr      - array
         i        - current index that will use or not for arr
         path     - current subsequence we are summing
        solutions - all solutions found
  """
  # Set defaults
  if i is None:
    i = len(arr) - 1
  if solutions is None:
    solutions = []
  if path is None:
    path = []

  # Base Cases
  if s == 0:
    solutions.append(path[:])
    return solutions

  if i < 0 or s < 0:
    return

  # Try with arr[i] in path
  if arr[i] <= s:
    solve(arr, s-arr[i], i-1, [arr[i]] + path, solutions)

  # Try with arr[i] not in path
  solve(arr, s, i-1, path, solutions)

  return solutions

Test

arr = [1, 2, 3, 4, 5]
print(solve(arr, 10))

Output

[[1, 4, 5], [2, 3, 5], [1, 2, 3, 4]]

a function that return all possible sub arrays that sum up to a specific given number (need not to be a continuous sub array)

2 Answers2