admin管理员组

文章数量:1123054

递归

文章目录

  • 前言
  • 一、什么是回溯算法？
  • 二、解决什么问题可用到回溯？
  • 三、回溯算法模板
  • 四、题目
    • 1.组合
    • 2.组合总和
    • 3.组合总和II
    • 4.组合总和 III
    • 5.电话号码的字母组合
    • 6.分割回文串
    • 7.数组切分
    • 8.复原 IP 地址
  • 总结

前言

一、什么是回溯算法？

回溯算法也叫回溯搜索法，是一种搜索方式。
有递归就会有回溯，回溯是递归的副产品，是递归的小弟。
回溯主要往树的深度进行搜索，遇到终止条件，就会往回上一层，继续向深度走，最终会得到所有的可能出现的结果，则递归结束。

二、解决什么问题可用到回溯？

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

三、回溯算法模板

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

分析：

  1. 必须有终止条件，终止条件是结束向树深度寻找的动作。
  2. backTracking(路径，选择列表) “选择列表”要具体的条件设计。
  3. for循环表示的是树的宽度。
  4. return；终止决定了递归的深度。
    以上这些4点，结合下面例题进行理解。

四、题目

1.组合

链接
来源力扣77题
问题描述：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

代码如下：

class Solution {List<List<Integer>> res=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();public List<List<Integer>> combine(int n, int k){backtracking(n,k,1);return res;}public void backtracking(int n,int k,int index){//数组的长度==k，则结束递归if(path.size()==k){res.add(new ArrayList<>(path));return;}//若剩余的数,不足以组成k个数。i<=n可进行优化//已选择的数量为 path.size()//未选择的数量为 k-path.size()//在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历for (int i=index;i<=n - (k - path.size()) + 1;i++){path.add(i);//添加数到pathbacktracking(n,k,i+1);//这里为什么是i+1，因为是向后选择，所以下一层的初始位置是i+1。path.removeLast();//移除上一个添加的数}}}

2.组合总和

链接
来源力扣39题

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

代码如下：

class Solution {List<List<Integer>> res=new ArrayList<>();LinkedList<Integer> list=new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {//进行升序排序Arrays.sort(candidates);backtracking(candidates,target,0,0);return res;}public void backtracking(int[] candidates, int target,int sum,int startIndex){if(sum==target){res.add(new ArrayList<>(list));return;}for (int i=startIndex;i<candidates.length;i++){if (sum+candidates[i]>target)//如果路径之和大于目标值，则直接结束循环，后面的数也无需再选取。{break;}//记录路径之和sum+=candidates[i];list.add(candidates[i]);backtracking(candidates,target,sum,i);//这里为什么i了，因为同一个数可无限被选取，所以下一层的初始位置是i。sum-=candidates[i];list.removeLast();}}}

3.组合总和II

链接
来源力扣40题

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

代码如下：

class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>(); Boolean[] used;//记录每个数的状态public List<List<Integer>> combinationSum2(int[] candidates, int target) {used=new Boolean[candidates.length];Arrays.fill(used,false);//关键：排序Arrays.sort(candidates);AddPath(candidates,target,0,0);return result;}public void AddPath(int[] candidates,int target,int sum,int startindex){if(sum==target){result.add(new ArrayList<>(path));return;}for (int i=startindex;i<candidates.length;i++){//如上一题的情况if(sum+candidates[i]>target){break;}//进行树层去重操作，//used[i-1]==false表示的是同一层的节点，已被使用//used[i-1]==true表示同一树枝已被使用过if(i>0&&candidates[i]==candidates[i-1]&& !used[i-1]){continue;}used[i]=true;sum+=candidates[i];path.add(candidates[i]);AddPath(candidates,target,sum,i+1);//这里为什么是i+1,因为每个数字在每个组合中只能使用 所以下一层要在i+1位置上进行遍历。used[i]=false;Integer last = path.removeLast();sum-=last;}}
}

4.组合总和 III

链接
来源力扣216题
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

代码如下：

class Solution {List<List<Integer>> res=new ArrayList<>();LinkedList<Integer> list=new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {//因为数字只能使用1到9，startIndex的坐标为1开始遍历backtracking(k,n,0,1);return res;}public void backtracking(int k, int n,int sum,int startIndex){if(list.size()==k){if(sum==n){res.add(new ArrayList<>(list));}return;}for (int i=startIndex;i<=9;i++){if(sum+i>n){break;}sum+=i;list.add(i);//这里为什么是i+1，因为每个数字 最多使用一次，所以下一层就要从i+1的位置进行遍历。startindex和递归的层数没有直接关系。backtracking(k,n,sum,i+1);sum-=i;list.removeLast();}}
}

5.电话号码的字母组合

链接
来源力扣17题
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

—

示例 1：

输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,“b”,“c”]

代码如下：

class Solution {List<String> res=new ArrayList<>();//存储数字对应的字符串String[] num={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};public List<String> letterCombinations(String digits) {if(digits.length()==0) return res;backTrack(digits,new StringBuffer(),0);return res;}public void backTrack(String digits,StringBuffer st,int startIndex){if(st.length()==digits.length()){res.add(new String(st));return;}//获取相应数字的字符串String target=num[Integer.valueOf(digits.charAt(startIndex)-'0')];for (int i=0;i<target.length();i++){st.append(target.charAt(i));//这里为什么是startIndex+1，因为这是对应digits的下标，//下一层要获取digits[i+1]，digits.length表示这棵树的深度。backTrack(digits,st,startIndex+1);st.deleteCharAt(st.length()-1);}}
}

6.分割回文串

链接
来源力扣131题

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

输入：s = “a”
输出：[[“a”]]

代码如下：

class Solution {List<List<String>> res=new ArrayList<>();LinkedList<String> path=new LinkedList<>();public List<List<String>> partition(String s) {backtracking(s,0);return res;}public void backtracking(String s,int index){//当分割线下标在最后，则已经是分割完成。if(index==s.length()){res.add(new ArrayList<>(path));return;}for (int i=index;i<s.length();i++){//字符串截取，index上一个分割线后的，后面的字符串的初始位置。String substring = s.substring(index, i + 1);if(isPrime(substring)){path.add(substring);backtracking(s,i+1);//这里为什么i+1,因为字符串往后面分割的，所以下一层的要i+1开始进行遍历。path.removeLast();}}}//判断是否是回文串public boolean isPrime(String st){int start=0,end=st.length()-1;while (start<end){if(st.charAt(start)!=st.charAt(end)){return false;}start++;end--;}return true;}
}

7.数组切分

链接
蓝桥杯2022年第十三届省赛真题

题目描述

已知一个长度为 N 的数组：A1, A2, A3, …AN 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个，最多 N 个) 连续的子数组，并且每个子数组中包含的整数恰好可以组成一段连续的自然数。

例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法：

{1}{3}{2}{4}：每个单独的数显然是 (长度为 1 的) 一段连续的自然数。

{1}{3, 2}{4}：{3, 2} 包含 2 到 3，是 一段连续的自然数，另外 {1} 和 {4} 显然也是。

{1}{3, 2, 4}：{3, 2, 4} 包含 2 到 4，是 一段连续的自然数，另外 {1} 显然也是。

{1, 3, 2}{4}：{1, 3, 2} 包含 1 到 3，是 一段连续的自然数，另外 {4} 显然也是。

{1, 3, 2, 4}：只有一个子数组，包含 1 到 4，是 一段连续的自然数。
输入格式
第一行包含一个整数 N。第二行包含 N 个整数，代表 A 数组。
输出格式
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
样例输入

4
1 3 2 4

样例输出

5

提示

对于 30% 评测用例，1 ≤ N ≤ 20.

对于 100% 评测用例，1 ≤ N ≤ 10000.

代码如下：

import java.util.LinkedList;
import java.util.Scanner;public class Main {static LinkedList<Integer> path =  new LinkedList<>();static int res = 0, mod = 1000000007;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = sc.nextInt();dfs(a, 0);System.out.println(res % mod);}private static void dfs(int[] a, int startindex) {int n = a.length;if (startindex == n) {res ++;return;}for (int i = startindex; i < n; i++) {if (check(a, startindex, i)) {path.add(i);dfs(a, i + 1);path.removeLast();}}}private static boolean check(int[] a, int l, int r) {int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;for (int i = l; i <= r; i++) {if (a[i] > max) max = a[i];if (a[i] < min) min = a[i];}return max - min == r - l;}
}

8.复原 IP 地址

链接
来源力扣93题

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：

输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

代码如下：

//这复杂度有点高，后面会进一步优化剪枝。但代码会比较清晰简单易懂。
class Solution {List<String> res=new ArrayList<>();LinkedList<String> path=new LinkedList<>();public List<String> restoreIpAddresses(String s) {backTracking(s,0);return res;}public void backTracking(String s,int index){//path数组里的字符串==4    if(path.size()==4){//切割位置到达字符串的末尾，则将path添加resif(index==s.length()){res.add(GetAim(path));}return;}for (int i=index;i<s.length();i++){String substring = s.substring(index, i + 1);//判断截取的字段是否合法,不合法直接结束if((substring.length()>=2&&substring.charAt(0)=='0')||Integer.valueOf(substring)>255){break;}path.add(substring);backTracking(s,i+1);//和上面的例题同理path.removeLast();}}//获取path数组的字符串public String GetAim(LinkedList<String> path){String st="";for (int i=0;i<path.size();i++){if(i>0){st=st+"."+path.get(i);}else {st+=path.get(i);}}return st;}
}

总结

目前就这么些题目，后续会进行不定时更新。

本文标签： 递归

版权声明：本文标题：递归 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1686805041a38134.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。