Learning Journal

2/12/2024

Combination Sum - 2nd attempt

function combinationSum(candidates: number[], target: number): number[][] {
    

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

    const result:number[][] = [];
    const comb:number[] = [];
   
    const backtrack = (remain:number, start: number) => {

        for(let i = start; i < candidates.length; i++) {
            if(remain === candidates[i]) {
                result.push([...comb, candidates[i]]);
                break;
            }
            else if(remain < candidates[i]){
                break;
            }
            else {
                comb.push(candidates[i]);
                backtrack(remain - candidates[i], i);
                comb.pop();
            }
        }

        
    } 


    backtrack(target,0);

    return result;

  
};function combinationSum(candidates: number[], target: number): number[][] {
    

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

    const result:number[][] = [];
    const comb:number[] = [];
   
    const backtrack = (remain:number, start: number) => {

        for(let i = start; i < candidates.length; i++) {
            if(remain === candidates[i]) {
                result.push([...comb, candidates[i]]);
                break;
            }
            else if(remain < candidates[i]){
                break;
            }
            else {
                comb.push(candidates[i]);
                backtrack(remain - candidates[i], i);
                comb.pop();
            }
        }

        
    } 


    backtrack(target,0);

    return result;

  
};

THE PROBLEM

I made two improvements in this attempt.

This is a backtracking approach to the problem. In the previous attempt, I let the algorithm go over the ending point (where remain equals or less than 0), then I added the combination to the result array. This time, I let the for loop check for the ending point before calling backtrack, so that the algorithm doesn't need to make another recursive call.

Secondly, I just recognized that if the candidates array is sorted in an ascending order, we don't need to iterate all of the candidates array because we know that if remain <= candidates[i], remain will also be less than candidates[i + 1], so, we can stop there.

There is one point to remember. If you don't want to repeat the same combination with a different order, you need to set i to start, so the recursive calls do not need to consider the elements that their parents have already considered.

Revised by ChatGPT

In this attempt, I implemented two improvements to the backtracking approach for solving the problem. Compared to the previous attempt where the algorithm continued past the endpoint (where remain is less than or equal to 0) and then added the combination to the result array, I've made a significant adjustment. Now, the for loop checks for the endpoint before invoking backtrack. This change prevents unnecessary recursive calls when the endpoint is reached or exceeded.

Secondly, I realized the efficiency of sorting the candidates array in ascending order. Once sorted, it becomes unnecessary to iterate through the entire array of candidates. This is because if remain is less than or equal to candidates[i], it will also be less than candidates[i + 1], allowing for an early termination of the loop.

An important strategy to avoid repeating the same combination in a different order involves setting i to start. This ensures that recursive calls do not reconsider elements already accounted for by their parent calls, maintaining the uniqueness of each combination.