## faqts : Computers : Programming : Languages : Python : Snippets

##### + Search    Did You Find This Entry Useful? 4 of 6 people (67%) answered YesRecently 2 of 2 people (100%) answered Yes

### Entry

##### Find sublist with sum X (was: Online programming contest)

Jul 5th, 2000 10:03
Nathan Wallace, Hans Nowak, Snippet 318, Tim Peters

```"""
Packages: maths
"""
"""
> ...
> My algortihm (not shown) would be recursive up to depth n (given n
> numbers).   Any ideas what depth of recursion the contest would allow?
No idea.
> What depth of recursion is a reasonable limit to aim for in Python?
At least thousands.
> My guess is that given n numbers, brute force is O(2^n) and O(2^(n/2))
> should be attainable.  Any math experts have the real answers?
Yes, O(2^(n/2)) is attainable:  split the list in equal-size halves A and
B, compute all possible sums from A (O(2^(n/2))) and B (ditto) separately,
then see whether there's a sum from A and a sum from B that have the
desired total (again O(2^(n/2)) using e.g. a hash table).  Note that this
is a one-shot trick, though:  it breaks the problem into two subproblems
of a *different* nature, so it's the end of that road.  I don't know of a
better worst-case general solution than that.
Agree with Aaron it's a hard problem; disagree that it's 0/1 knapsack in
disguise (which is about maximizing a linear function, not about hitting a
specific value on the nose); it *is* an instance of the "sum of subsets"
problem family, though.
The attached solves a slightly more general problem and usually works well
in "real life" problems (more like low-order polynomial time than
exponential, although its worst case in contrived examples is indeed
O(2^n)).  The same bounding functions (for weeding out impossibilities)
can be used in a recursive framework that requires no more than O(n)
space; but since the approach does work so well in real life, and frequent
recursion is relatively very expensive in Python, I use this non-recursive
(but potentially space-gobbling) version.
Note that this approach buys some of its efficiency at the cost of being
hard to extend to find *all* solutions.  That's easy in a straightforward
recursive version, though -- so use that if you're trying to teach the
neighborhood supermarket checkout droid all the unseen possibilities open
to them for making correct change <wink>.
anyone-got-change-for-6-billion-people?-ly y'rs  - tim
"""
def find_sublist_with_sum(nlist, target):
"""Return sublist of nlist whose elements add up to target.
Return None if no such sublist exists.
The return value never contains 0.
The return value is [] if target is 0.
The order of elements in the return value is not defined.
If more than one sublist sums to target, which one is
returned is not defined.
Examples:
xxx([1, 2, 3], 3) == [1, 2] or [2, 1] or 
xxx([-2, 1, -1, 0, 0], 0) == []
xxx([-2, 1, -1, 0, 0], 1) == 
xxx([1, 2], 8) == None
xxx([1, 2, 3, 4], 6) == [1, 2, 3] or [2, 4] or etc
"""
# Sort to help the bounds checks cut off impossibilities early;
# not needed for correctness, and other ordering strategies may
# be more helpful depending on the expected cases.
# Note that reverse-sorting guarantees the answer will be given
# in non-decreasing order.
ns = nlist[:]
ns.sort()
ns.reverse()
# find smallest and largest possible sums
max_left = min_left = 0
for n in ns:
if n >= 0:
max_left = max_left + n
else:
min_left = min_left + n
# map partial sum to last element added into it
partial = {0: 0}
inpartial = partial.has_key
# instrumentation
global _nconsidered, _nsurvivors
# Each iteration of the outer loop leaves partial containing
# all distinct possible sums taken from sublists ending at n.
# Except that some of those are trash:  if a partial sum plus
# min_left is greater than target, all possible completions
# are greater than target, so that partial sum can be ignored;
# similarly if a partial sum plus max_left is less than target.
for n in ns:
if n >= 0:
max_left = max_left - n
else:
min_left = min_left - n
for sum in partial.keys():
_nconsidered = _nconsidered + 1
this = sum + n
if min_left <= target - this <= max_left and \
not inpartial(this):
_nsurvivors = _nsurvivors + 1
partial[this] = n
if this == target:
return _construct_sublist(partial, target)
assert min_left == max_left == 0
return None
def _construct_sublist(partial, target):