39. Combination Sum

Leetcode link

题目简介

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

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

要求我们选取 candidates 中任意数字组成数组，使得数组所有元素之和等于 target

数组中的数字可以被使用多次

题目要求我们返回所有符合条件的数组

解题思路

涉及到选择的题目，我们可以使用回溯的思路来求解

具体来说我们需要维护一个数组 arr 来保存当前符合条件的元素

每次回溯的终止条件是 sum(arr) >= target

如果两者相等，代表我们找到了一个符合条件的数组，可以把它保存起来

如果总和大于 target，我们直接终止这次回溯，继续遍历下一个元素

由于 candidates 中的每个元素都可以使用多次，所以我们每次回溯的时候，都需要遍历一次整个 candidates

Javascript

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
    const len = candidates.length
    const res = []

    const backtracking = (index, sum, arr) => {
        if (sum > target) {
            return
        }
        if (sum === target) {
            res.push([...arr])
            return
        }
        for (; index >= 0; index--) {
            arr.push(candidates[index])
            backtracking(index, sum + candidates[index], arr)
            arr.pop()
        }
    }

    backtracking(len - 1, 0, [])
    return res
};