洛龙区网站制作建设费用,海南网站定制,做商城网站的企业,wordpress本地utc目录 回溯算法一、什么是回溯算法1、基本思想#xff1a;2、一般步骤#xff1a; 二、题目带练1、全排列2、组合3、子集 三、公式总结 回溯算法
一、什么是回溯算法
回溯算法#xff08;Backtracking Algorithm#xff09;是一种解决组合问题、排列问题、选择问题等一类问… 目录 回溯算法一、什么是回溯算法1、基本思想2、一般步骤 二、题目带练1、全排列2、组合3、子集 三、公式总结 回溯算法
一、什么是回溯算法
回溯算法Backtracking Algorithm是一种解决组合问题、排列问题、选择问题等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解当发现当前选择不符合要求时就回溯到之前的状态然后尝试其他的选择。
1、基本思想
从问题的起始点开始进行尝试每次选择一个可能的路径。如果发现当前选择无法达到解决问题的目标就回退到上一个状态尝试其他的选择。不断地重复上述过程直到找到解决问题的路径或者遍历完所有可能的选择。
2、一般步骤
确定问题的解空间和约束条件。从解空间中选择一个可能的选择进入下一步。判断当前选择是否符合约束条件如果符合继续深入尝试下一步如果不符合回退到上一步。重复上述步骤直到找到解或者遍历完所有可能的选择。
二、题目带练
1、全排列
题目地址 分析 看到这道题的描述不难想到如果我们要找出所有的排列方式就要遍历n次数组每次选择一个不重复元素排列在上次循环选择的元素后面那这就出现了一个问题怎么对一个数组遍历n次
显然这是不太可能实现的因为n是不确定的但是我们可以换一种思路通过深度来代表遍历次数也就是我们常说的回溯算法。
根据题意我们应当设递归出口为 当前递归的深度 数组的长度if(depth nums.length)同时保存当前的排列方式到集合中。ans.add(new ArrayList(path));每次递归的过程中我们需要遍历一次数组for(int i 0; i nums.length; i)判断当前的元素是否被使用过if(used[i])如果没被使用那么就将其记录下来并且标记为使用过继续进入递归path.add(nums[i]); used[i] true;。当这次递归结束时dfs(nums,depth 1,used);撤销当前元素的使用标记并且移除记录的集合。path.remove(path.size() - 1); used[i] false;
效果就是调用方法后先选择元素1path.add(nums[0]); used[0] true;再次调用方法记录深度1dfs(nums,depth 1,used);此时发现1已经被选择过了开始选择2path.add(nums[1]); used[1] true;调用递归深度1dfs(nums,depth 1,used);同理1,2被标记为使用过的元素继续选择3path.add(nums[2]); used[2] true;然后递归结束。这里会退回到深度为2的那次选择因为2之后还有别的元素可以选择选择3后发现只有2可以选了首选项为1的递归结束依次类推得到所有排列方式。
代码如下
class Solution {public ListListInteger ans new ArrayList();public ListInteger path new ArrayList();public ListListInteger permute(int[] nums) {boolean[] used new boolean[nums.length];dfs(nums,0,used);return ans;}public void dfs(int[] nums,int depth,boolean[] used){if(depth nums.length){ans.add(new ArrayList(path));return;}for(int i 0; i nums.length; i){if(used[i]){continue;}path.add(nums[i]);used[i] true;dfs(nums,depth 1,used);path.remove(path.size() - 1);used[i] false;}}
}2、组合
题目地址 分析
这道题与全排列的区别在于全排列需要全部选择而这道题不一定要全部选择并且每个组合只能有一次所以面对这道题我们不能按照和之前同样的思路去解因为无法排除同样组合的组合顺序问题。
那么我们要如何作出改动呢
其实很简单我们只需要让每次循环的起始值变为当前的深度即可同时也不需要判断是否使用过了因为我们只会向后找不会从前开始往后找了。
class Solution {ListInteger temp new ArrayListInteger();ListListInteger ans new ArrayListListInteger();public ListListInteger combine(int n, int k) {dfs(1, n, k);return ans;}public void dfs(int depth, int n, int k) {if (temp.size() k) {ans.add(new ArrayListInteger(temp));return;}for(int i depth;i n;i){temp.add(i);dfs(i 1, n, k);temp.remove(temp.size() - 1);}}
}3、子集
题目地址 分析
大家看这道题可能会发现是不是和组合有点相似区别在哪呢区别在于子集的选择长度不一定是n而是[0,n]。
其实我们只需要每次回溯都记录一次结果就好了。
class Solution {ListInteger list new ArrayList();ListListInteger result new ArrayList();public ListListInteger subsets(int[] nums) {dfs(0,nums);return result;}public void dfs(int current, int[] nums){result.add(new ArrayList(list));if(current nums.length){return;}for(int i current; i nums.length; i){list.add(nums[i]);dfs(i 1, nums);list.remove(list.size() - 1);}}
}三、公式总结
如果认真看完的朋友可以发现对于这种基础的回溯题目我们都可以通过循环回溯来解决问题只需要根据具体问题来更改我们的循环条件即可。
当然这么做不一定是最好的还有许多可以优化的地方只是说大部分情况可以通过这种循环的方式来解决问题。
