Combination Sum II

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:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
  candidates.sort(function(a, b) {
    return a - b;
  });

  var len = candidates.length;
  var res = [];
  var ans = [];

  dfs(0, 0);

  function dfs(index, sum) {
    if (sum > target)
      return;

    if (sum === target) {
      ans.push(res.concat());
      return;
    }

    for (var i = index; i < len; i++) {
      // Point!
      // remove the duplicate combinations
      if (i > index && candidates[i] === candidates[i - 1])
        continue;
      res.push(candidates[i]);
      dfs(i + 1, sum + candidates[i]);
      res.pop();
    }
  }

  return ans;
};

Combination Sum III

Find all possible combinations of $k$ numbers that add up to a number $n$, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:
Input: k = 3, n = 7

Output:

[[1,2,4]]

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */

function dfs(arr, last, num, k, sum, n) {
  if (num === k && sum === n) {
    var tmp = arr.map(function(item) {
      return item;
    });

    ans.push(tmp);
    return;
  }

  if (num > k || sum > n ) 
    return;

  for(var i = last + 1; i <= 9; i++) {
    arr[arr.length] = i;
    dfs(arr, i, num + 1, k, sum + i, n);
    arr.pop();
  }
}

var combinationSum3 = function(k, n) {
  ans = [];
  for(var i = 1; i <= 9; i++)
    dfs([i], i, 1, k, i, n);
  return ans;
};

Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
  // ans[i] 表示组成 i 的方案数
  var ans = [];
  ans[0] = 1;

  for (var i = 1; i <= target; i++) {
    ans[i] = 0;
    for (var j = 0, len = nums.length; j < len; j++) {
      var item = nums[j];
      if (i - item < 0)
        continue;
      // (i - item) + item = i
      ans[i] += ans[i - item];
    }
  }

  return ans[target];
};