回溯算法 js_回溯算法代码

回溯算法 js_回溯算法代码回溯算法是算法设计中的一种回溯算法是一种渐进式寻找并构建问题解决方式的策略回溯算法会先从一个可能的动作开始解决问题,如果不行,就回溯并选择另一个动作,直到将问题解决使用场景有很多路在这些路中,有死路和出路通常需要递归来模拟所有的路leetcode46:全排列解题思路要求:1所有排列情况;2没有重复元素有出路有死路使用回溯算法解题步骤用递归模拟出所有情况遇到包含重复元素的情况,就回溯收集所有到达递归终点的情况,并返回code//时间复杂度O.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

  • 回溯算法是算法设计中的一种
  • 回溯算法是一种渐进式寻找并构建问题解决方式的策略
  • 回溯算法会先从一个可能的动作开始解决问题,如果不行,就回溯并选择另一个动作,直到将问题解决
  • 使用场景
    • 有很多路
    • 在这些路中,有死路和出路
    • 通常需要递归来模拟所有的路

leetcode 46: 全排列

在这里插入图片描述

  • 解题思路
    • 要求:1所有排列情况; 2没有重复元素
    • 有出路有死路
    • 使用回溯算法
  • 解题步骤
    • 用递归模拟出所有情况
    • 遇到包含重复元素的情况,就回溯
    • 收集所有到达递归终点的情况,并返回

code

// 时间复杂度O(n!) n的阶乘
var permute = function(nums) { 
   
	const res = []
	const backtrack = (path) => { 
   
		if (path.length === nums.length) { 
   
			res.push(path)
			return 
		}
		nums.forEach(n => { 
   
			if (path.includes(n)) return // 死路:包含元素
			backtrack(path.concat(n))
		})
	}
	backtrack([])
}

leetcode78:子集 在这里插入图片描述

  • 解题思路
    • 要求:1所有子集; 2没有重复元素
    • 有出路有死路
    • 使用回溯算法
  • 解题步骤
    • 用递归模拟出所有情况
    • 保证接的数字都是后面的数字
    • 收集所有到达递归终点的情况,并返回

code

// 时间复杂度O(2^N) 空间复杂度O(N)
var subsets = function(nums) { 
   
	const res = []
	const backtrack = (path, l, start) => { 
   
		if (path.length === l) { 
   
			res.push(path)
			return
		}
		for (let j = start; j < nums.length; j++) { 
   
			backtrack(path.concat(nums[j]), l, j + 1)
		}
	}
	for (let i = 0; i <= nums.length; i++) { 
   
		backtrack([], i, 0)
	}
	return res
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/186020.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号