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

0 comments:

Blogroll

Follow this blog by Email

Popular Posts