4
\$\begingroup\$

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?

\$\endgroup\$
2
  • \$\begingroup\$ "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. \$\endgroup\$
    – Peilonrayz
    Mar 6 at 3:43
  • \$\begingroup\$ @Peilonrayz let me try at different time in that case. Can you guide on how you plotted the graph \$\endgroup\$
    – Dr._Duck
    Mar 6 at 17:01

1 Answer 1

3
\$\begingroup\$
  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.

enter image description here

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()
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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