CODEWITHSUNDEEP
javascriptalgorithm
myTest532 myTest532
myTest532 myTest532

Reputation: 2381

Combination Sum in Javascript

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

Upvotes: 1

Views: 2238

Answers (1)

Yousaf
Yousaf

Reputation: 29282

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

Upvotes: 4

Related Questions