Combination Sum in Javascript

Question

I'm trying to create the combination sum algorithm in Javascript.

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

My solution is using recursive method.

var combinationSum = function(candidates, target) {
    let ans = []
    if(candidates === null || candidates.length === 0)
        return ans;
    
    candidates.sort();

    let current = []
    findNumbers(candidates, target, 0, current, ans);
    return ans;
};

const findNumbers = function(candidates, target, i, current, ans){
    if(target === 0){
        const temp = current.slice();
        ans.push(temp);
        return;
    }
    
    for(let j=i; j<candidates.length; j++){
        if(target < candidates[j])
            return;
        current.push(candidates[j]);
        findNumbers(candidates, target - candidates[j], j, current, ans);
        current.pop();
    }
}

It works with basic tests. However, with the input below it fails.

candidates = [3,12,9,11,6,7,8,5,4], target = 15

My output is:

[[3,3,3,3,3],[3,3,3,6],[3,3,4,5],[3,3,9],[3,4,4,4],[3,4,8],[3,5,7],[3,6,6],[4,4,7],[4,5,6],[5,5,5],[6,9],[7,8]]

The correct output should be:

[[3,3,3,3,3],[3,3,3,6],[3,3,4,5],[3,3,9],[3,4,4,4],[3,4,8],[3,5,7],[3,6,6],[3,12],[4,4,7],[4,5,6],[4,11],[5,5,5],[6,9],[7,8]]

I have no clue why it is not inserting in the ans array the solution [3,12] and [4,11]. Any idea why?

Thanks

Answer 1

You are not getting the correct result because you are not sorting the array correctly

By default, sort function sorts the array items by converting them to strings and then comparing their UTF-16 code units, which means your candidates array

[3, 12, 9, 11, 6, 7, 8, 5, 4]

is sorted as

[11, 12, 3, 4, 5, 6, 7, 8, 9]

You need to provide a custom function to sort the numbers correctly

candidates.sort((a, b) => a - b);