组合总数2

[louzhedong]

题目

出处：LeetCode 算法第40题

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

思路

和上一题一样，都是采用递归遍历的做法，但由于每个数字只能用一次，所以递归的时候不能递归当前的项，需要递归下一项。

解答

var combinationSum2 = function (candidates, target) {
  var strresult = [];  // 定义一个字符串的数组用来去重
  var result = [];
  var temp = [];
  var sum = 0;
  candidates.sort(function (a, b) {
    return a - b;
  })
  DFS(candidates, sum, 0, target, temp, result, strresult);
  return result;
};

function copy(array) {
  var result = [];
  for (var i = 0, len = array.length; i < len; i++) {
    result.push(array[i]);
  }
  return result;
}

function DFS(candidates, sum, level, target, temp, result, strresult) {
  if (sum > target) {
    return;
  }
  if (sum == target && strresult.indexOf(temp.join('')) < 0) {
    result.push(copy(temp));
    strresult.push(temp.join(''));
    return;
  }
  for (var i = level; i < candidates.length; i++) {
    sum += candidates[i];
    temp.push(candidates[i]);
    DFS(candidates, sum, i + 1, target, temp, result, strresult); // 递归下一项
    temp.pop();
    sum -= candidates[i];
  }
}