leetcode 40 组合总和2 js-白红宇

leetcode 40 组合总和2 js

阅读量：668 次

发布时间：2019-03-15

本文共 1150 字，大约阅读时间需要 3 分钟。

要解决这个问题，我们可以使用回溯法来找出所有可以组成目标数的组合。以下是详细的解决方案：

方法思路

排序数组：首先对候选数组进行排序，这样可以确保我们每次选择的是有序的元素，避免重复选择相同的元素。

递归函数设计：使用一个递归函数进行深度优先搜索，参数包括当前和、起始索引和临时数组。

剪枝条件：如果当前和超过目标数，直接返回，避免不必要的递归调用。

重复元素处理：在递归过程中，确保不重复选择相同的元素，特别是在数组中有连续的相同元素时。

结果记录：当和等于目标数时，将当前组合添加到结果集中。

解决代码

combinationSum2 = function (candidates, target) {    candidates.sort((a, b) => a - b);    const res = [];    const dfs = (sum, start, temp) => {        if (sum === target) {            res.push(temp.slice());            return;        }        if (sum > target) {            return;        }        for (let i = start; i < candidates.length; i++) {            if (i > start && candidates[i] === candidates[i - 1]) {                continue;            }            temp.push(candidates[i]);            dfs(sum + candidates[i], i + 1, temp);            temp.pop();        }    };    dfs(0, 0, []);    return res;};