combination Sum DSA

 function combsum(arr,sum1)

    {

        newarr = [];

        backtrack(arr,0,sum1,newarr)

    }

 

function backtrack(arr,start,sum1,newarr)

    {

        if(sum1<0)

            return

        if(sum1==0)

        {

            console.log(newarr)

        }

        else

        {

            for(var i = start;i<arr.length;i++)

                {

                    newarr.push(arr[i])

                    backtrack(arr,i,sum1-arr[i],newarr)

                    newarr.pop(newarr.length-1)

                }

        }

    }

console.log(combsum([1,2,4,6,8],8));

 

Output:-

[1, 1, 1, 1, 1, 1, 1, 1]

 [1, 1, 1, 1, 1, 1, 2]

 [1, 1, 1, 1, 2, 2]

 [1, 1, 1, 1, 4]

 [1, 1, 2, 2, 2]

 [1, 1, 2, 4]

 [1, 1, 6]

 [2, 2, 2, 2]

 [2, 2, 4]

 [2, 6]

 [4, 4]

 [8]