算法-经典递归解决排列组合

文章目录

前言

如何正确的处理递归

所有的递归都分为带路径的递归和不带路径的递归, 我们之前学二叉树的时候基本上都是带路径的递归, 所有的递归其实都是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);
                }
            }
        }
    }
}