trekhleb / trekhleb/javascript-algorithms

Infinite recursion in combinationSum

Open
#308 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
JavaScript
Stars
197k
Forks
31k
PR merge metrics
No merged PRs in 30d

Description

Details:

combinationSum fails with Maximum call stack size exceeded.
It seems that there is an infinite recursion in it.

Step to reproduce: combinationSum([0], 1)

Bug 1: presence of 0 produces an infinite loop
Bug 2: presence of small entries compared to target produces a stack size exceeded - combinationSum([1], 100000)

Fix

I can issue a PR with the fix.

How did I find it?

Thanks to property based testing framework fast-check.
The property was the following:

import fc from 'fast-check';

fc.assert(
    fc.property(
        fc.set(fc.nat()),
        fc.nat(),
        (elements, target) => {
            const combinations = combinationSum(elements, target);
            const combinationsStr = combinations.map(arr => arr.join(','));
            // no duplicates
            expect([...new Set(combinationsStr)]).toEqual(combinationsStr);
            // right sum
            for (const comb of combinations)
                expect(comb.reduce((a,b) => a+b, 0)).toBe(target);
        }
    )
)

Or:

for any elements - array of unique positive integers, target - positive integer
the output of combinationSum(elements, target) does not contain any duplicates
and all its entries sum to target

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Locate the combinationSum implementation and any related tests, then reproduce the reported calls with combinationSum([0], 1) and combinationSum([1], 100000). Confirm that inputs containing zero or small values no longer overflow the stack, while returned combinations remain duplicate-free and sum to the target.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
data
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.