问题描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为：
[[7],[2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为：
[[2,2,2,2],[2,3,3],[3,5]
]

示例 3:

输入: candidates = [2], target = 1,
所求解集为：
[]

示例 4:

输入: candidates = [1], target = 1,
所求解集为：
[[1]
]

示例 5:

输入: candidates = [1], target = 2,
所求解集为：
[[1,1]
]

解法一

解题思路:

使用回溯法，从左到右依次尝试每个数字，如果当前数字小于等于目标数，则将其加入当前组合中，递归调用函数处理剩余部分，然后回溯，移除当前数字，尝试下一个数字。

/** @lc app=leetcode.cn id=216 lang=javascript** [216] 组合总和III*/// @lc code=start
function combinationSum3(candidates, target) {const res = [];function backtrack(remain, comb, start) {if (remain === 0) {res.push([...comb]);return;}for (let i = start; i < candidates.length; i++) {if (candidates[i] > remain) break;comb.push(candidates[i]);backtrack(remain - candidates[i], comb, i);comb.pop();}}backtrack(target, [], 0);return res;
}
// @lc code=end