题目描述

给定一个数组 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]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题一开始做的时候是在每一处都做从小到大排序，来保证结果。

后来发现只要对一开始的数组进行排序就可以保证了，而且还可以剪枝加速。

这里 js 版本用了 JSON 对数据进行 stringify，然后当做 hash 来作结果判定。

  1. /**
  2.  * @param {number[]} candidates
  3.  * @param {number} target
  4.  * @return {number[][]}
  5.  */
  6. var combinationSum2 = function(candidates, target) {
  7.     let ret = [];
  8.     let res = [];
  9.     let cand = [];
  10.     let hash = [];
  12.     function find(start, target) {
  13.         for (let i = start; i < cand.length; i++) {
  14.             let item = cand[i];
  15.             if (item > target) return ;
  16.             res.push(item);
  17.             if (item === target) {
  18.                 pushRes(res.slice());
  19.             } else {
  20.                 find(i + 1, target - item);
  21.             }
  22.             res.pop();
  23.         }
  24.     }
  26.     function pushRes(res) {
  27.         let resStr = JSON.stringify(res);
  28.         if (hash.indexOf(resStr) < 0) {
  29.             ret.push(res);
  30.             hash.push(resStr);
  31.         }
  32.     }
  34.     cand = candidates.sort(function(a, b) {
  35.         return a - b;
  36.     });
  37.     // console.log(cand);
  38.     find(0, target);
  39.     return ret;
  40. };

这里注意一下：我自己一开始也翻了低级错误，js 的 sort 需要自写函数，从小到大可以写作：

  1. let a = [4, 1, 3];
  2. a.sort(function(a, b) {
  3.   return a - b;
  4. });
  6. // es6
  7. a.sort((a, b) => a - b);