combinations_target.js

by raviteja gunda

JavaScript

function get_combinations(arr,target){
    arr = arr.sort((a,b) => a - b);

    let result = [];
    console.log(arr);

    util(arr,target,0,[],result);
    //console.log('result', result);
    return result;
}
var depth = "";
function util(arr,target,indx,slate,result){
    if(target == 0){
        console.log(depth, '**found match**', slate);
        result.push(slate.slice());
        return;
    }

    if(indx == arr.length || target < 0){
        return;
    }

    let end = indx;
    //console.log(depth, 'util start indx', indx, 'end', end, 'target', target, 'result', result);
    
    while(end < arr.length && arr[end] == arr[indx]){
        end++;
    }

    console.log(depth, 'a util indx', indx, 'end', end, 'target', target, 'slate', slate);
    depth = depth + "\t"
    util(arr,target,end,slate,result);
    
    let count = 1;
    var depthInner = depth;
    while(count <= end-indx){
        slate.push(arr[indx]);
        //target = target - (count*arr[indx]);
        console.log(depthInner, 'count', count, '<= end-index', end-indx);
        console.log(depthInner, 'target original', target);
        console.log(depthInner, 'sending target without count', target - arr[indx]);
        console.log(depthInner, 'b util indx', indx, 'end', end,'sending target', target - (count*arr[indx]), 'slate', slate);
        depthInner = depthInner + "\t";
        util(arr,target - count * arr[indx],end,slate,result);
        depthInner = depthInner.replace("\t", "");
        count++;
        console.log(depthInner, 'b util returned count:', count, 'end-index=', end-indx);
    }
    
    count = 1;
    while(count <= end-indx) {
        slate.pop();
        console.log(depth, 'pop ', slate);
        count++
    }
    depth = depth.replace("\t", "");
    console.log('');

}

//console.log(get_combinations([42, 68, 35, 1, 70, 25, 79, 59, 63, 65, 6, 46, 82, 28, 62, 92, 96, 43, 28, 37, 92, 5, 3, 54, 93], 83));
console.log(get_combinations([3, 3, 3, 1, 6, 7], 7));