文章来源于网络收集而来,版权归原创者所有,如有侵权请及时联系!
组合总和
解题思路
回溯 + 剪枝。
- 剪枝:sum > target 结束当前递龟;sum === target 路径加入解集;限制下次递龟的起点避免重复组合。
- ×:当前组合和之前生成的组合重复了。
- △:当前求和 > target,不能选下去了,返回。
- ○:求和正好 == target,加入解集,并返回。
代码实现
const combinationSum = (candidates: number[], target: number): number[][] => {
const res: number[][] = [];
const backTrace = (start: number, temp: number[], sum: number): void => {
if (sum > target) return;
if (sum === target) res.push([...temp]);
for (let i = start; i < candidates.length; i++) {
temp.push(candidates[i]); // 选这个数
backTrace(i, temp, sum + candidates[i]);
temp.pop(); // 撤销选择,继续尝试选同层右边的数
}
};
backTrace(0, [], 0);
return res;
};
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论