40.组合总和II.md

思路

按照上一题的思路，过滤掉重复的元素，注意索引的位置

代码

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
  if (!candidates.length) return [];
  let res = [], path = [];
  candidates.sort((a, b) => a - b)

  function findTarget(arr, target, begin, path) {
    if (target === 0) {
      res.push(path.slice());
      return;
    }
    if (target < arr[begin]) return;

    for(let i = begin; i < arr.length; i ++) {
      let cur = arr[i]
      if (i > begin && cur == arr[i - 1]) continue;
      path.push(cur);
      findTarget(arr, target - cur, i + 1, path);
      path.pop();
    }
  }

  findTarget(candidates, target, 0, path);

  return res;
};

复杂度分析

时间复杂度 $O(2^N)$

空间复杂度 $O(N)$