回溯法分为组合,子集,排列等问题,下面分别就这几个问题进行总结.
1.总体架构
总体来说,回溯法像是在遍历一棵树,而这棵树的深度,由回溯的终止条件以及for循环内部的变量控制组成
LinkedList<Integer> temp = new LinkedList<>();//暂存数据的链表
List<List<Integer>> re = new ArrayList<>();//待返回的结果集
public void backtracing(int[] nums, int startIndex, int[] used){
//三个参数分别表示 nums待遍历的数组,通常是题目中给出的数组
//startIndex遍历的开始位置,并不一定是必须的,取决于题目类型(如果是一个数组的组合问题则一般需
//要)
//used 则用于父子结点间去重,在同父亲结点间的去重则在本函数内部定义一个hashMap或者used数组
if(){
//此处填写的是满足遍历结束的条件,通常为temp数组(或者linkedList)的长度满足给定的条件
//将满足条件的temp加入到re中
re.add(new ArrayList(temp));
//在添加结束后是否是使用return则需要根据题目的条件判断:
//如果是全排列,组合问题这种,也就是说都已经遍历到这个树的叶子结点的这种问题,应当采用return
//而若是子序列问题,比如寻找递增子序列(力扣491),整棵树还需要继续向下进行遍历,则不需要return
}
//当然如果我们为了达到在同父结点的层内去重的目的,要在此处建立一个HashMap,或者used数组,
//不过需要注意的是,如果再这里建立的uesed数组,他的意义和传参进来的used数组并不一样,传参进来的
//used数组是用来标识数组中的下标,也就是说,数组中的数字按顺序来看是否被使用,而此处则是标记同
样的
//数字是否被使用.所以used的数组的范围应该是nums数组中数字的范围,而不是nums数组的长度,传参进
//来的used的范围是nums数组长度(目的是为了一对一表示数组中的元素)此处的给出示例:力扣46题,以及
//自己写的力扣47题的used数组,(自己写的放在了力扣刷题专栏中)
HashMAP<Integer,Integer> map = new HashMap<>();//本层去重(如果需要)
//这里需要判断map中的key和value的相对关系了
if(map.getOrDefault(nums[i],0) >= 1){
//这里满足当前条件则说明在本层,这个数字已经出现过一次了
continue;//如果满足条件的话,且需要去重
}
for(int i = ?; i < nums.length; i++){
//在此处,i的起始值是一个问号,需要根据是否使用startIndex来进行修改,如果使用startIndex
//那么i的值为startIdex,否则为0
//对于是否使用startIndex给出示例: 对于[1,2,3]这个数组来说,如果求的是子序列问题,或者组合
//问题,也就是说只能出现[1,2],[1,3]这种按照原始的相对顺序出现,则需要startIndex,若求的是
//排列问题,也就是说要求[3,2,1]这种情况出现,则不能使用startIndex,因为要是使用了,则 3 对
//应着最后的位置,没办法再向前遍历到1,2的位置
if(添加一些判断条件,比如要求递增序列){
}
temp.add(nums[i]);
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
//!!!!!!
//注意这个map不回溯!因为层间去重,回溯就没意义了!!!!!!!!!
used[i] = 1 ;//将数组的当前位置记为使用过的形式,这种遍历方式是会让子元素不再使用
//解决的问题主要是当出现重复的数字的时候,不超过重复次数的使用重复数字
backtracing(nums, i + 1, used);//注意此处若采用了startIndex则向下一层应该是i+1,而不
//是startIndex+1
temp.remove(temp.size() - 1);//撤销修改
used[i] = 0;
}
}2.组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
class Solution {
List<String> re = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return re;
}
//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//迭代处理
backTracking(digits, numString, 0);
return re;
}
StringBuilder t = new StringBuilder();
public void backTracking(String digits, String[]numString, int cur){
if(cur == digits.length()){
re.add(t.toString());
return;
}
String str = numString[digits.charAt(cur) - '0'];
for(int i = 0; i < str.length(); i++){
t.append(str.charAt(i));
backTracking(digits,numString,cur+1);
t.deleteCharAt(t.length()-1);
}
}
}3.子序列问题
此处的子序列问题使用了层间去重的操作
层间去重使用了两个版本的方法,分别为HashMap以及used数组,注意此处的used数组和排列问题的used数组并不一样,无论从意义和大小来说.
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
class Solution {
LinkedList<Integer> li = new LinkedList<>();
List<List<Integer>> re = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
get(nums, 0);
return re;
}
public void get(int[] nums, int startIndex){
if(li.size() >= 2){
re.add(new ArrayList(li));
// return;
}
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = startIndex; i < nums.length; i++){
if (li.size() > 0 && nums[i] < li.getLast()){
continue;
}
if (map.getOrDefault(nums[i], 0) >= 1){
continue;//说明使用过了
}
li.add(nums[i]);
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
get(nums, i + 1);
li.remove(li.size() - 1);
}
}
}class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtracking(nums,0);
return res;
}
private void backtracking (int[] nums, int start) {
if (path.size() > 1) {
res.add(new ArrayList<>(path));
}
int[] used = new int[201];
for (int i = start; i < nums.length; i++) {
if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||
(used[nums[i] + 100] == 1)) continue;
used[nums[i] + 100] = 1;
path.add(nums[i]);
backtracking(nums, i + 1);
path.remove(path.size() - 1);
}
}
}4.排列问题
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]自己写的代码段如下
class Solution {
LinkedList<Integer> temp = new LinkedList<>();
List<List<Integer>> re = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
int[] used = new int[nums.length];
get(nums, used);
return re;
}
public void get(int[] nums, int[] used){
if(temp.size() == nums.length){
re.add(new ArrayList(temp));
return;
}
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
//优先判断是否是使用过的数字used数组(因为如果先判断了是否是层间去重,可能直接就跳过了)
//如果使用过则continue而不是return,因为continue就直接跳过向下一层的循环了
if(used[i] == 1 || map.getOrDefault(nums[i],0) >= 1){//层间重复的数字,跳过
continue;
}
used[i] = 1;
temp.add(nums[i]);
map.put(nums[i], map.getOrDefault(nums[i],0) + 1);
get(nums,used);
used[i] = 0;//回溯
temp.remove(temp.size() - 1);
// map不回溯
}
}
}解释:hashMap负责层间去重,used负责重复元素的使用次数不超过重复次数~
以1 1 3为例子画图说明
5.回溯代码是否设置返回值的问题:
如果是要寻找出全部的路径则不用添加返回值,但是要是只需要找到一条路径,就应当设置返回值.类比树的返回值设置.
1.如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回
2.如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
3.如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。
带返回值的回溯法举例如下:
题目描述:
对应的代码如下:
class Solution {
private LinkedList<String> re ;//在回溯过程中如果符合要求就直接返回
private LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
//按照第二个元素的升序排列
Collections.sort(tickets, (a,b)->(a.get(1).compareTo(b.get(1))));
path.add("JFK");
boolean[] used = new boolean[tickets.size()];
backtracing((ArrayList)tickets, path, used);
return re;
}
public boolean backtracing(ArrayList<List<String>> tickets, LinkedList path, boolean[] used){
if(path.size() == tickets.size() + 1){
re = new LinkedList(path);
return true;
}
for(int i = 0 ; i < tickets.size(); i++){
if(!used[i] && tickets.get(i).get(0).equals(path.getLast())){
path.add(tickets.get(i).get(1));//没被使用过
used[i] = true;
if(backtracing(tickets, path, used)){
return true;
}
used[i] = false;
path.remove(path.size()-1);
}
}
return false;
}
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/88870.html
