trekhleb / trekhleb/javascript-algorithms
Infinite recursion in combinationSum
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 ofcombinationSum(elements, target)does not contain any duplicates
and all its entries sum to target
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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