算法-经典递归解决排列组合
前言
如何正确的处理递归
所有的递归都分为带路径的递归和不带路径的递归, 我们之前学二叉树的时候基本上都是带路径的递归, 所有的递归其实都是DFS(深度优先搜索), 对于如何用递归解决问题这件事, 我们需要把递归想象为一个"黑匣子" , 在解决问题的时候尝试寻找子问题, 然后复用该函数, 新手在处理递归问题的时候, 通常喜欢对递归问题进行展开, 固然, 对递归问题进行全部展开是一种直观的理解递归问题的方式, 但是对递归问题进行全部的展开, 往往会很难以理解, 下次遇到问题的时候还是会一头雾水, 所以我建议, 在用递归处理问题的时候, 我们先去抽象的理解递归问题, 相信递归函数一定能处理这个问题, 然后在深入递归函数的本质, 这样理解起来往往会比较简单…, 下面的经典递归问题的解析我们都将用这种方式来解决…
如何理解递归与回溯
递归回溯其实是相辅相成的, 递归的过程中天然就带有回溯, 但是有时候我们不去用到这个点, 其实就是一种恢复现场的技巧, 个人认为恢复现场这个词更能体现出回溯的真正含义
1. 获取字符串的所有字串
题目解析
这道题的题目是获取字符串的所有字串, 比如 “abcdefg” 字串的数量是 2^7 == 128个, 其实就是我们高中所学的集合相关的知识, 求集合的所有子集的问题(二项式定理), 上面的字符串太长不好举例子, 我们用 “abc” 举例子, 该字符串的字串有8个, 分别是
“a”, “b”, “c”, “ab”, “ac”, “bc”, “abc”, " "
递归分析
首先把我们的函数想象为一个黑盒, 我们的函数为func, 在经过func的作用之后就可以得到所有的字串的集合, 所以出现了问题的复现
求"abcd"所有字串 = 带有"a" + 求"bcd"的所有字串
求"abcd"所有字串 = 不带有"a" + 求"bcd"的所有字串
注意这里的不带有"a", 其实就是我们等下需要进行恢复现场的点…
现在看我们的代码实现
public class Main{
public static void main(String[] args) {
//输入程序
Scanner in = new Scanner(System.in);
String s = in.next();
//参数处理与函数调用
char[] chars = s.toCharArray();
StringBuilder sp = new StringBuilder();
HashSet<String> set = new HashSet<>();
getSubStrings(chars, 0, sp, set);
//迭代器遍历输出
Iterator<String> it = set.iterator();
while (it.hasNext()) {
System.out.print(it.next() + "/ ");
}
}
public static void getSubStrings(char[] chars, int index, StringBuilder sp, HashSet<String> set) {
//递归的终止条件
if (index == chars.length) {
String temp = sp.toString();
if (!set.contains(temp)) {
set.add(temp);
}
return;
}
//加上当前字符的情况
sp.append(chars[index]);
getSubStrings(chars, index + 1, sp, set);
//下面的这一步, 就是我们所说的回溯, 因为想要得到不含有该字符的所有字串就需要删除该字符
sp.deleteCharAt(sp.length() - 1);
getSubStrings(chars, index + 1, sp, set);
}
}
上述代码的实现逻辑就是通过sp不断拼接, 当我们的下标是终止位置的时候就进行输出
代码执行结果
代码的调用逻辑图, 由于该代码的调用逻辑比较复杂, 我们把递归调用的逻辑图用下图来表示("abc为例子), 图中的黑线是DFS向下递归的过程, 我们的(√ / ×) 代表的是该位置的字符时候进行拼接, 我们向上返回的时候正好是我们的该字符删除的时期, 还是那句话, 递归的逻辑图一般比较复杂, 我们理解递归的方式应该是抽象与具体相结合…
下面的代码是对我们的上面的代码的改进, 通过一个char数组和一个size来管控path的控制, 其实就是子集手动的模拟了一个栈的结构
public static String[] generatePermutation2(String str) {
char[] s = str.toCharArray();
HashSet<String> set = new HashSet<>();
f2(s, 0, new char[s.length], 0, set);
int m = set.size();
String[] ans = new String[m];
int i = 0;
for (String cur : set) {
ans[i++] = cur;
}
return ans;
}
public static void f2(char[] s, int i, char[] path, int size, HashSet<String> set) {
if (i == s.length) {
set.add(String.valueOf(path, 0, size));
} else {
path[size] = s[i];
f2(s, i + 1, path, size + 1, set);
f2(s, i + 1, path, size, set);
}
}
2. 数组的子集(无重复)
题目描述就是上面描述的那样, 其实就类似于我们上面的寻找字符串的所有子序列一样, 我们而且这个是没有相同的元素的, 所以最后也不涉及去重的相关操作, 我们快速过掉这个题
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
getSubSets(nums,0,new ArrayList<>());
return res;
}
private void getSubSets(int[] nums,int index,List<Integer> list){
//递归的终止条件
if(index == nums.length){
List<Integer> temp = new ArrayList<>();
for(int elem : list){
temp.add(elem);
}
res.add(temp);
}else{
list.add(nums[index]);
getSubSets(nums,index + 1,list);
//回溯过程
list.remove(list.size() - 1);
getSubSets(nums,index + 1,list);
}
}
}
3. 数组的子集(有重复)
这个问题跟上面的问题一样, 但是不一样的是, 我们的内部元素使用重复的, 这会导致我们最终的结果出先问题, 这时候我们就想, 那这个题我们还按照之前字符串子集的那个思路, 最后用HashSet去重一下就好了么, 实则不然, 我们看下面的这个例子
假如我们的集合是 [ 4 , 4 , 1 , 4 ]
我们如果用字符串去重的方式写这一道题, 我们就会出现下面的bug
我们的集合的子集可能会有(√是有,x是无)
[√, √, √, x] —> [ 4 , 4 , 1 ]
[√, x,√, √ ] —> [ 4 , 1 , 4 ]
这两个集合明显都是子集, 如果用HashSet去重的话二者都会被添加进结果, 但显然这个结果是不对的, 根据我们这道题目的要求, 我们的每个子集的元素的数目如果一致也是认为是一样的, 也就是
4 1 4 和 4 4 1 其实只能添加一个, 那如何解决这个问题呢
常规排序 + DFS展开
用我们之前的思路解决这道题是很容易的, 我们只需要先将数组进行排序, 就可以用常规的HashSet进行去重操作, 因为排序过了之后, 之前的重复的组别(比如 441 和 414 )就会被排序颠覆给自然的擦除掉, 代码实现如下
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
//我们的常规解法就是之前学的那个返回字符串的所有子集的思路
ArrayList<Integer> list = new ArrayList<>();
HashSet<List<Integer>> set = new HashSet<>();
Arrays.sort(nums);
func(nums,0,list,set);
return res;
}
private void func(int[] nums,int index,ArrayList<Integer> list,HashSet<List<Integer>> set){
//递归的终止条件
if(index == nums.length){
List<Integer> temp = (List<Integer>)list.clone();
if(!res.contains(temp)) res.add(temp);
}else{
list.add(nums[index]);
func(nums,index+ 1 ,list,set);
list.remove(list.size() - 1);
func(nums,index + 1,list,set);
}
}
}
排序 + 剪枝 + DFS展开
显然, 上面的解法是不够好的, 时间复杂度是 2^n * n, 那有没有一种更好的方式来解决这个问题呢
我们拿下面的这个例子举例
假如一个集合排序之后的结果是 [ 1 1 1 1 1 2 2 2 2 4 4 5 5 6 6 8 8 ]
我们尝试用分组的策略来简化递归的过程
我们的问题被拆解为 :
全集合的子集 = n 个 1 + [ 2 2 2 2 4 4 5 5 6 6 8 8 ] 子集的数量
其中 n 的值为 [ 0, 5 ]
剪枝的原理实现
为什么这个逻辑就可以简化代码, 是因为如果不进行这样设计的话, 我们原来的 5 个 1 会进行全部展开, 一共的数目情况是 2 ^ 5 == 32, 但是如果用这种分组的角度思考的话, 我们就只有6种情况(1的个数), 所以自然会加快了递归的过程, 代码实现如下
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 先对数组进行排序
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
ArrayList<Integer> arr = new ArrayList<>();
func(nums, 0, arr, res);
return res;
}
private void func(int[] nums, int index, ArrayList<Integer> arr, List<List<Integer>> res) {
// 递归的终止条件
if (index == nums.length) {
ArrayList<Integer> tempList = new ArrayList<>();
for (int elem : arr) {
tempList.add(elem);
}
res.add(tempList);
} else {
int j = index + 1;
// 把j下标移动到不同的第一个元素的位置
while (j < nums.length && nums[index] == nums[j])
j++;
int sz = 0;
for (sz = 0; sz <= (j - index); ++sz) {
//进行不同数目的组内数字添加
for (int k = 0; k < sz; ++k) {
arr.add(nums[index]);
}
func(nums, j, arr, res);
//回溯的过程, 要恢复现场
for (int k = 0; k < sz; ++k) {
arr.remove(arr.size() - 1);
}
}
}
}
}
4. 字符大小写全排列
这道题我们插到这里作为一个练习, 本题的思路就是上面的DFS求子序列的思路(注意回溯的逻辑)
class Solution {
public List<String> letterCasePermutation(String s) {
List<String> res = new ArrayList<>();
char[] sc = s.toCharArray();
StringBuilder sp = new StringBuilder();
HashSet<String> set = new HashSet<>();
letterSubPath(sc, 0, sp, res, set);
return res;
}
public void letterSubPath(char[] chars, int index, StringBuilder sp, List<String> res, HashSet<String> set) {
// 递归的终止条件
if (chars.length == index) {
String temp = sp.toString();
if (!set.contains(temp)) {
set.add(temp);
res.add(temp);
}
} else {
if (chars[index] >= '0' && chars[index] <= '9') {
sp.append(chars[index]);
letterSubPath(chars, index + 1, sp, res, set);
sp.deleteCharAt(sp.length() - 1);
} else {
if (chars[index] >= 'A' && chars[index] <= 'Z') {
sp.append(chars[index]);
letterSubPath(chars, index + 1, sp, res, set);
sp.deleteCharAt(sp.length() - 1);
sp.append((char) (chars[index] + 32));
letterSubPath(chars, index + 1, sp, res, set);
sp.deleteCharAt(sp.length() - 1);
} else {
sp.append(chars[index]);
letterSubPath(chars, index + 1, sp, res, set);
sp.deleteCharAt(sp.length() - 1);
sp.append((char) (chars[index] - 32));
letterSubPath(chars, index + 1, sp, res, set);
sp.deleteCharAt(sp.length() - 1);
}
}
}
}
}
5. 全排列(无重复)
这个题的意思就是说对于一个集合来说, 求他的所有的排列
比如一个集合[ 3 1 2 ], 一共 n! 种情况
我们可能的排列是[ 3 1 2 ] [ 3 2 1 ] [ 2 3 1 ] [ 2 1 3 ] [ 1 2 3 ] [ 1 3 2 ]
递归的逻辑分析
那么这道题如何用递归来理解呢, 我们的函数的func是来求全部的排列, 所以得到下面的关系
全部元素的全排列 = 不同的元素在0下标的全排列 + 剩余元素的全排列
子问题的递推出现了复现, 所以就可以写出下面的递归的逻辑
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
permute(nums, 0, res);
return res;
}
private void permute(int[] nums, int index, List<List<Integer>> res) {
//递归的终止条件
if (index == nums.length) {
List<Integer> temp = new ArrayList<>();
for (int elem : nums) {
temp.add(elem);
}
res.add(temp);
} else {
for (int j = index; j < nums.length; ++j) {
swap(nums, index, j);
permute(nums, index + 1, res);
//一定要回溯恢复现场(不然会有重复的情况存在)
swap(nums, index, j);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复杂度是 n! * n
6. 全排列(有重复)
这个题目比上面的就只有一点, 就是加一个HashSet去重
代码实现如下
class Solution {
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
permuteUnique(nums, 0, res);
return res;
}
private void permuteUnique(int[] nums, int index, List<List<Integer>> res){
if(index == nums.length){
List<Integer> temp = new ArrayList<>();
for (int elem : nums) {
temp.add(elem);
}
res.add(temp);
}else{
HashSet<Integer> set = new HashSet<>();
for (int j = index; j < nums.length; ++j) {
if(!set.contains(nums[j])){
set.add(nums[j]);
swap(nums, index, j);
permuteUnique(nums, index + 1, res);
swap(nums, index, j);
}
}
}
}
}
原文地址：https://blog.csdn.net/2301_81486828/article/details/140442787
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！