Problem

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.

Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, ... , ak) must be in non-descending order. (ie, a1 <= a2 <= ... <= ak). The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7,
A solution set is:

[7] 
[2, 2, 3] 

JavaScript Code

function combinationSum(candidates, target) {
    var result = [];
 
    if(candidates == null || candidates.length == 0) return result;
 
    var current = [];
    candidates.sort();
 
    combinationSumHelper(candidates, target, 0, current, result);
 
    return result;
}
 
function combinationSumHelper(candidates, target, j, curr, result){
   if(target == 0){
       var temp = curr.slice();
       result.push(temp);
       return;
   }
 
   for(var i=j; i<candidates.length; i++){
       if(target < candidates[i]) 
            return;
       curr.push(candidates[i]);
       combinationSumHelper(candidates, target - candidates[i], i, curr, result);
       curr.pop(); 
   }
}

With Unique Combinations

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used ONCE in the combination.

Note:
1) All numbers (including target) will be positive integers.
2) Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
3) The solution set must not contain duplicate combinations.

JavaScript Code

var result = [];

function combinationSum(num, target) {
    result = [];
    if(num == null || num.length == 0)
        return result;
 
    num.sort();            
 
    var temp = [];    
    getCombination(num, 0, target, temp, result);
}
function getCombination(num, start, target, temp){
    if(target == 0){
        var t = JSON.parse(JSON.stringify(temp));
        if(indexOf(result, t, arraysIdentical)  == -1) {
            result.push(t);
        }
        return;
    }
 
    for(var i=start; i<num.length; i++){
        if(target < num[i])
            continue;
 
        temp.push(num[i]);
        getCombination(num, i+1, target-num[i], temp, result);
        temp.pop();
    }
}

function arraysIdentical(arr1, arr2) {
    var i = arr1.length;
    if (i !== arr2.length) {
        return false;
    }
    while (i--) {
        if (arr1[i] !== arr2[i]) {
            return false;
        }
    }
    return true;
}

function indexOf(arr, val, comparer) {
    for (var i = 0, len = arr.length; i < len; ++i) {
        if ( i in arr && comparer(arr[i], val) ) {
            return i;
        }
    }
    return -1;
}

3 comments:

  1. Excellent mind bending code :-)

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Software Development Company in Malaysia
    We are one of the best Award-Winning Software Development Company in Malaysia specialized in IOS application development, android app development company, Web and mobile app development in Malaysia.

    ReplyDelete

Blogroll

Follow this blog by Email

Popular Posts