Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

• First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
• Second node is labeled as 1. Connect node 1 to node 2.
• Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

/**
 * Definition for undirected graph.
 * function UndirectedGraphNode(label) {
 *     this.label = label;
 *     this.neighbors = [];   // Array of UndirectedGraphNode
 * }
 */

/**
 * @param {UndirectedGraphNode} graph
 * @return {UndirectedGraphNode}
 */
var cloneGraph = function(graph) {
  if (!graph)
    return null;

  var hash = {};

  return dfs(graph);

  function dfs(node) {
    var label = node.label;
    var newNode = new UndirectedGraphNode(label);
    hash[label] = newNode;

    for (var i = 0, len = node.neighbors.length; i < len; i++) {
      var item = node.neighbors[i];
      if (hash[item.label] !== undefined)
        newNode.neighbors.push(hash[item.label]);
      else
        newNode.neighbors.push(dfs(item));
    }

    return newNode;
  }
};

Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
  var ans = [];
  ans[0] = 0;

  for (var i = 0, len = coins.length; i < len; i++) {
    var item = coins[i];
    for (var j = 0; j + item <= amount; j++) {
      if (ans[j] === undefined)
        continue;
      if (ans[j + item] === undefined)
        ans[j + item] = ans[j] + 1;
      else 
        ans[j + item] = Math.min(ans[j + item], ans[j] + 1);
    }

  }

  return ans[amount] === undefined ? -1 : ans[amount];
};

Combination Sum

Given a set of candidate numbers (C) (without duplicates) 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.
• 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]
]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var ans, res;

function dfs(index, sum, candidates, target) {
  if (sum === target) {
    var tmp = res.map(function(item) {
      return item;
    });

    ans.push(tmp);
    return;
  }

  for (var i = index, len = candidates.length; i < len; i++) {
    if (sum + candidates[i] > target) continue;
    res.push(candidates[i]);
    dfs(i, sum + candidates[i], candidates, target);
    res.pop();
  }
}

var combinationSum = function(candidates, target) {
  ans = [];
  candidates.sort(function(a, b) {
    return a - b;
  });
  
  // choose the first number
  for (var i = 0, len = candidates.length; i < len; i++) {
    res = [candidates[i]];
    dfs(i, candidates[i], candidates, target);
  }

  return ans;
};