40. Combination Sum II

Leetcode link

题目简介

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

题目给我们一个数组 candidates 以及数字 target

要求我们找出数组 candidates 中加总为 target 的所有子数组

子数组需要升序排序

解题思路

这题我们尝试用回溯的思路来求解

首先需要给 candidates 进行排序，这样以来我们可以在回溯过程中剪枝减少计算量

在回溯的过程中我们有两个重要的判断：

1. 如果当前元素与上一个元素重复了，我们需要跳过
2. 如果当前子数组的综合已经超过了 target，我们也需要跳过

Javascript

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

    const backtrack = (start, restTarget, curCandidates) => {
        if (restTarget === 0) {
            res.push([...curCandidates])
            return
        }

        for (let i = start; i < candidates.length; i++) {
            if(i > start && candidates[i] === candidates[i-1]) {
                continue
            }
            if(candidates[i] > restTarget) {
                return
            }

            curCandidates.push(candidates[i])
            backtrack(i+1, restTarget - candidates[i], curCandidates)
            curCandidates.pop()
        }
    }

    backtrack(0, target, [])
    return res
};