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

Question

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.

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. — Peilonrayz, 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 — Dr._Duck, Commented Mar 6 at 17:01

Peilonrayz · Accepted Answer · 2024-03-07 05:34:53Z

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

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

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

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

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))

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()

Stack Exchange Network

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

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged
python
performance
or ask your own question.

Hot Network Questions

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

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged pythonperformance or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
python
performance
or ask your own question.