返回介绍

组合总和

发布于 2024-09-16 00:06:32 字数 1004 浏览 0 评论 0 收藏 0

题目内容

解题思路

回溯 + 剪枝。

  • 剪枝: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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文