# What could be the more optimised way to get all unique subarray which equals to a target

I am trying to solve Combination Sum II on LeetCode. I was able to derive a recursive solution for the problem but it is not optimised as it only beats 10% of the solutions.

1. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output:
[
[1, 1, 6],
[1, 2, 5],
[1, 7],
[2, 6]
]

Example 2:

Input: candidates = [2, 5, 2, 1, 2], target = 5
Output:
[
[1, 2, 2],
[5]
]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

def combinationSum2(self, candidates, target):
res = []
def helper(arr,index,curr_sum,ans):
if curr_sum == target:
#ans = sorted(ans)
if ans not in res:
res.append(ans)
return
if len(arr) == index or curr_sum > target:
return

helper(arr,index+1,curr_sum + arr[index],ans +[arr[index]])

while len(arr)-1 > index and arr[index] == arr[index+1]:
index += 1
helper(arr,index+1,curr_sum,ans)

return res

return helper(sorted(candidates),0,0,ans=[])

What could I improve in my code or
how can I optimise it better by following the same recursive approach?

• "it only beats 10% of the solutions" did you try running the tests multiple times? I have had algorithms be both top and bottom 10% -- only difference is I ran the same code at different times. I only ask because I wrote my own solution which should be somewhat performant and I'm getting almost identical results to you. Commented Mar 6 at 3:43
• @Peilonrayz let me try at different time in that case. Can you guide on how you plotted the graph Commented Mar 6 at 17:01

1. First lets clean up your code.

def combination_sum_2(candidates: list[int], target: int) -> list[list[int]]:
def inner(terms: list[int], curr_sum: int, index: int) -> None:
if curr_sum == target:
if terms not in res:
res.append(terms)
return

if index == len(candidates) or target < curr_sum:
return

inner(terms + [candidates[index]], curr_sum + candidates[index], index + 1)

while index + 1 < len(candidates) and candidates[index] == candidates[index+1]:
index += 1

inner(terms, curr_sum, index + 1)

res: list[list[int]] = []
candidates = list(sorted(candidates))
inner([], 0, 0)
return res

2. You are wasting time by filtering duplicates within inner rather than once outside inner.

while index + 1 < len(candidates) and candidates[index] == candidates[index+1]:
index += 1

def combination_sum_2(candidates: list[int], target: int) -> list[list[int]]:
def inner(index: int, curr_sum: int, terms: list[int]) -> None:
if curr_sum == target:
if terms not in res:
res.append(terms)
return

if index == len(candidates) or target < curr_sum:
return

inner(index + 1, curr_sum + candidates[index], terms + [candidates[index]])
inner(index + 1, curr_sum, terms)

res: list[list[int]] = []
candidates = list(sorted(set(candidates)))
inner(0, 0, [])
return res

3. Using recursion for looping is a bad idea in Python.

>>> def loop(n: int) -> int:
...     def inner(n: int) -> int:
...         if not n:
...             return 0
...         else:
...             return inner(n - 1)
...     assert 0 <= n
...     return inner(n)
...
>>> loop(1000)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 8, in loop
File "<stdin>", line 6, in inner
File "<stdin>", line 6, in inner
File "<stdin>", line 6, in inner
[Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

As such rather than using the FP looping mechanic we should just loop over a range.

if index == len(candidates) or ...:
return

...

inner(terms, curr_sum, index + 1)

def combination_sum_2(candidates: list[int], target: int) -> list[list[int]]:
def inner(terms: list[int], curr_sum: int, index: int) -> None:
if curr_sum == target:
if terms not in res:
res.append(terms)
return

if target < curr_sum:
return

for i in range(index, len(candidates)):
v = candidates[index]
inner(terms + [v], curr_sum + v, i + 1)

res: list[list[int]] = []
candidates = list(sorted(set(candidates)))
inner(0, 0, [])
return res

4. Given the constraints we can pre-calculate the end index. When curr_sum is 13 and the target 30 then the max option is 17. Checking if 18+ sum to 30 is a waste of time.

• 1 <= candidates[i] <= 50
• 1 <= target <= 30

We can build an array containing the index of the highest value which can be added to. Then we use range(index, high_index[target - curr_sum]).

import bisect

def rstretch__index(values: list[int], length: int) -> list[int]:
return [
bisect.bisect(values, i) - 1
for i in range(length)
]

def combination_sum_2(candidates: list[int], target: int) -> list[list[int]]:
def inner(terms: list[int], curr_sum: int, lo: int, hi: int) -> None:
if curr_sum == target:
if terms not in res:
res.append(terms)
return

for i in range(lo, hi):
c = candidates[index]
inner(terms + [c], curr_sum + c, i + 1, high_index[target - curr_sum - c])

res: list[list[int]] = []
amounts = [0] * (target + 1)
for c in candidates:
if c <= target:
amounts[c] += 1
candidates = [i for i, c in enumerate(amounts) if c]
high_index = rstretch__index(candidates, target + 1)
if amounts[target]:
res.append([target])
inner([], 0, 0, len(candidates))
return res

5. I prefer using Pythons generator functions.

from typing import Iterator

def combination_sum_2(candidates: list[int], target: int) -> Iterator[tuple[int, ...]]:
def inner(terms: tuple[int, ...], curr_sum: int, lo: int, hi: int) -> Iterator[tuple[int, ...]]:
if curr_sum == target:
yield terms
return

for i in range(lo, hi):
c = candidates[index]
yield from inner(terms + [c], curr_sum + c, i + 1, high_index[target - curr_sum - c])

amounts = [0] * (target + 1)
for c in candidates:
if c <= target:
amounts[c] += 1
candidates = [i for i, c in enumerate(amounts) if c]
high_index = rstretch__index(candidates, target + 1)
yield from inner([], 0, 0, len(candidates))

6. We can move the if curr_sum == target into the loop by using if amounts[target - curr_sum]. We will need to handle if target is in candidates outside inner too.

def combination_sum_2(candidates: list[int], target: int) -> Iterator[tuple[int, ...]]:
def inner(terms: tuple[int, ...], curr_sum: int, lo: int, hi: int) -> Iterator[tuple[int, ...]]:
for i in range(lo, hi):
v = candidates[i]
curr = curr_sum + v
c = target - curr
if amounts[c] and i <= high_index[c]:
yield terms + (c,)
yield from inner(terms + (v,), curr, i + 1, high_index[target - curr])

amounts = [0] * (target + 1)
for c in candidates:
if c <= target:
amounts[c] += 1
candidates = [i for i, c in enumerate(amounts) if c]
high_index = rstretch__index(candidates, target + 1)
if amounts[target]:
yield (target,)
yield from inner((), 0, 0, len(candidates))

Note: No code in the answer has been validation tested.

Code to make graph:

import bisect
import collections
from typing import Iterator

def test_orig(candidates, target):
res = []
def helper(arr,index,curr_sum,ans):
if curr_sum == target:
#ans = sorted(ans)
if ans not in res:
res.append(ans)
return
if len(arr) == index or curr_sum > target:
return

helper(arr,index+1,curr_sum + arr[index],ans +[arr[index]])

while len(arr)-1 > index and arr[index] == arr[index+1]:
index += 1
helper(arr,index+1,curr_sum,ans)

return res

return helper(sorted(candidates),0,0,ans=[])

# A failed generalization of the 3SUM problem
def nsum(candidates: list[int], target: int) -> Iterator[tuple[int, ...]]:
candidates_seen_: dict[int, list[tuple[list[int], list[int]]]]
candidates_seen: dict[int, list[tuple[list[int], list[int]]]] = {}
for i, c in enumerate(candidates):
if c < target:
candidates_seen.setdefault(c, []).append(([i], [c]))
for _ in range(len(candidates)):
for i in range(len(candidates)):
a = candidates[i]
for j in range(i + 1, len(candidates)):
b = candidates[j]
for (indexes, c) in candidates_seen.get(target - a - b, []):
if j < indexes[0]:
yield a, b, *c
candidates_seen_ = {}
for c, seen in candidates_seen.items():
for (indexes, terms) in seen:
i = indexes[-1]
for j, d in enumerate(candidates[i + 1:], start=i + 1):
if c + d < target:
candidates_seen_.setdefault(c + d, []).append((indexes + [j], terms + [d]))
candidates_seen = candidates_seen_
if not candidates_seen:
break

def test_peil(candidates: list[int], target: int) -> list[tuple[int, ...]]:
return list(nsum(candidates, target))

def rstretch__index(values: list[int], length: int) -> list[int]:
return [
bisect.bisect(values, i) - 1
for i in range(length)
]

def nsum2(candidates: list[int], target: int) -> Iterator[tuple[int, ...]]:
def inner(terms: tuple[int, ...], curr_sum: int, lo: int, hi: int) -> Iterator[tuple[int, ...]]:
for i in range(lo, hi):
v = candidates[i]
curr = curr_sum + v
c = target - curr
if amounts[c] and i <= high_index[c]:
yield terms + (c,)
yield from inner(terms + (v,), curr, i + 1, high_index[target - curr])

amounts = [0] * (target + 1)
for c in candidates:
if c <= target:
amounts[c] += 1
candidates = [i for i, c in enumerate(amounts) if c]
high_index = rstretch__index(candidates, target + 1)
if amounts[target]:
yield (target,)
yield from inner((), 0, 0, len(candidates))

def test_peil2(candidates: list[int], target: int) -> list[tuple[int, ...]]:
return list(nsum2(candidates, target))

def nsum3(candidates: list[int], target: int) -> Iterator[tuple[int, ...]]:
amounts = [0] * (target + 1)
for c in candidates:
if c <= target:
amounts[c] += 1
candidates = [i for i, c in enumerate(amounts) if c]
high_index = rstretch__index(candidates, target + 1)

stack: list[tuple[int, Iterator[int], int]] = [(0, iter(range(len(candidates))), 0)]
while stack:
try:
i = next(stack[-1][1])
except StopIteration:
stack.pop()
continue
v = candidates[i]
curr_sum = stack[-1][2] + v
c = target - curr_sum
if amounts[c] and i <= high_index[c]:
s = iter(stack)
next(s, None)
yield tuple(f[0] for f in s) + (c,)
stack.append((i + 1, iter(range(i + 1, high_index[target - curr_sum])), curr_sum))

def test_peil3(candidates: list[int], target: int) -> list[tuple[int, ...]]:
return list(nsum3(candidates, target))

import functools
import random

import matplotlib.pyplot
import numpy
import graphtimer

random.seed(42401)

@functools.cache
def args_conv(size: int) -> tuple[list[int], int]:
return random.choices(range(101), k=int(size)), 30

def main():
fig, axs = matplotlib.pyplot.subplots()
axs.set_yscale('log')
axs.set_xscale('log')
(
graphtimer.Plotter(graphtimer.MultiTimer([test_orig, test_peil, test_peil2, test_peil3]))
.repeat(10, 10, numpy.logspace(0, 2, num=50), args_conv=args_conv)
.min()
).plot(axs, x_label='len(nums)')
fig.show()
matplotlib.pyplot.savefig('foo.png')

if __name__ == '__main__':
main()