1

Let's say my list is l = [1,2,3,4,5], and x = 8.

I'm thinking that I should iterate through the list using (for i in l:) and check to see if 2 numbers from the list add up to x-i using recursion. But that doesn't seem like the most efficient way to approach the problem.

Can someone show me a better way preferably in Python? Thanks

Nilesh
  • 20,521
  • 16
  • 92
  • 148
JennieOhyoung
  • 51
  • 5
  • 1
    Google for subset sum problem – thefourtheye Mar 04 '14 at 08:50
  • In the specific case of exactly 3 summing to a number, we can do much better than a general subset sum algorithm. This has been asked before; we should be able to find a duplicate question. – user2357112 Mar 04 '14 at 08:51
  • 4
    actually, he should be able to find it. why are you helping to lazy people? – Karoly Horvath Mar 04 '14 at 08:52
  • 1
    Because StackOverflow is harder to search than it should be. I've reanswered many questions simply because it was so much quicker than finding a duplicate, even though I knew there were duplicates. – user2357112 Mar 04 '14 at 08:54
  • I found http://stackoverflow.com/questions/1861516/onlogn-finding-3-numbers-that-have-a-sum-of-any-arbitrary-t-in-an-array , but it doesn't really give any code either. Accepted answer links to 3SUM on Wikipedia (http://en.wikipedia.org/wiki/3SUM). – RemcoGerlich Mar 04 '14 at 09:05
  • I have tried looking and I'm fairly new to this so I'm thankful for those that tried to help and point me in the right direction. – JennieOhyoung Mar 04 '14 at 18:31

3 Answers3

0

My idea would be to iterate through the list, but to keep three candidates in three variables. Then, as you progress through the list, you substitute them with new values based in order to approach the required value.

For example: c1 = 1; c2 = 2; c3 = 3; 1+2+3 =/= 8 next element is 4 try to substitute the smallest candidate, in this case c1: 4+2+3 > 8 try the next one, c2: 1+4+3 ==8 end

THe idea is to substitute a candidate based on how much the new some would approach, but not exceed, the desired value. If you iterate through the whole list, but found no suitable match, you can either run another iteration to be sure, or proclaim that the list does not contain any such numbers. This depends largely on whether the list is sorted.

This algorithm probably needs refinement, it's just from the top of my head, but I think it conveys an idea, which you can use.

Hope it helps.

user3209815
  • 357
  • 1
  • 11
  • 25
0

I cant say its a feasible or efficient solution for your question but it does work. 

>>> while True:
...     a = random.sample([1, 2, 3, 4, 5],  3)
...     if sum(a) == 8:
...         print a
...         break
... 
[3, 1, 4]
>>> while True:
...     a = random.sample([1, 2, 3, 4, 5],  3)
...     if sum(a) == 9:
...         print a
...         break
... 
[2, 3, 4]
Tanveer Alam
  • 5,185
  • 4
  • 22
  • 43
0

Thanks for everyone's help! I had no idea this type of question fall into a category called subset and more specifically rSum.

For those who are interested =)

l = [7,3,1,4,5]

def sum_to_x(l, x):

l.sort()
for i, val in enumerate(l):
    lower = 0
    upper = len(l)-1
    while lower < i < upper:
        temp = val + l[lower] + l[upper]
        if temp > x:
            upper -= 1
        elif temp < x:
            lower += 1
        else:
            yield l[lower], val, l[upper]
            lower += 1
            upper -= 1
JennieOhyoung
  • 51
  • 5