-1

I am given with an array arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and a target value trgt = 10. I need to find all possible combinations of subarrays such that sum of the elements of each subarray will result in the given target value trgt. I need to use Python to acomplish the task. I have found a similar discussion in here. However the given solution there only returns only one possible subarray instead of other valid subarrays. Any help pointing to obtaining all such subarrays will be very helpful. Thank you in advance.

Geek
  • 395
  • 1
  • 9
  • 4
    Have you tried anything by yourself yet? It's not a good practice to ask others to do your homework. You can share your approach, upto what extent you were able to work out and where you are actually failing. – taurus05 Feb 04 '19 at 02:14
  • The solution you refer to in your link ___does___ return all valid sub arrays, not only one. – SpghttCd Feb 04 '19 at 21:50

4 Answers4

1

The library of choice for getting combinations is itertools: 

import itertools as it
import numpy as np

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
trgt = 10

At first calculate the maximum length of a tuple that could result in trgt when summed up, even when it consists of the smallest numbers available:

maxsize = np.argwhere(np.cumsum(sorted(arr))>trgt)[0][0]

Then iterate from one to maxsize, let itertools create the corresponding combinations and save only those which sum up to trgt:

subsets = []
for size in range(1, maxsize+1):
    subsets.extend([t for t in it.combinations(arr, size) if sum(t)==trgt])

print(subsets)

#[(10,), (1, 9), (2, 8), (3, 7), (4, 6), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5), (1, 2, 3, 4)]
SpghttCd
  • 10,510
  • 2
  • 20
  • 25
  • Thanks for the solution. Actually I am looking for a solution that does not require to import other libraries. However anyway thank you for the help. – Geek Feb 04 '19 at 15:40
0

The following solution finds the subsets which adds to a target number: 

def subsetsum(array,num):

if num == 0 or num < 1:
    return None
elif len(array) == 0:
    return None
else:
    if array[0] == num:
        return [array[0]]
    else:
        with_v = subsetsum(array[1:],(num - array[0])) 
        if with_v:
            return [array[0]] + with_v
        else:
            return subsetsum(array[1:],num)
coderWorld
  • 602
  • 1
  • 8
  • 28
  • I have seen this solution before I have even posted the question. And as I mentioned this solution provides only one sunset out of many possible ones. What I wanted instead is all possible subsets. – Geek Feb 04 '19 at 15:36
0

Since you need to generate all solutions, you have solve it using brute force. One way to do this is by using bit masking like below

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
n = len(arr)
target = 10
res = []
for i in range(1<<n):
    s = 0
    subset = []
    for j in range(n):
        if i & (1<<(j)): # if this bit is set to 1
            subset.append(arr[j])
    if sum(subset) == target:
        res.append(subset)
print(res)  # [[1, 2, 3, 4], [2, 3, 5], [1, 4, 5], [1, 3, 6], [4, 6], [1, 2, 7], [3, 7], [2, 8], [1, 9], [10]]
xashru
  • 3,400
  • 2
  • 17
  • 30
0

This is the function of @harry on the SO-site of your link:

def subset(array, num):
    result = []
    def find(arr, num, path=()):
        if not arr:
            return
        if arr[0] == num:
            result.append(path + (arr[0],))
        else:
            find(arr[1:], num - arr[0], path + (arr[0],))
            find(arr[1:], num, path)
    find(array, num)
    return result

This is your data:

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
trgt = 10

the function from above applied to your data:

subset(arr, trgt)
#[(1, 2, 3, 4),
# (1, 2, 7),
# (1, 3, 6),
# (1, 4, 5),
# (1, 9),
# (2, 3, 5),
# (2, 8),
# (3, 7),
# (4, 6),
# (10,)]

So I'd suggest you to follow your link, upvote harry's answer and use it.

SpghttCd
  • 10,510
  • 2
  • 20
  • 25