概述
递归是一个非常经典的算法思想，很多问题都可以采用递归来解决，特别是对于树、字符串这类本身就具有递归性质的数据结构相关的问题，下面就列出几个可以用递归来解决的经典问题：
1. 字符串排列问题（不包含相同字符）
该问题要求求出字符串的所有排列，我们可以循环遍历整个字符串，将每次循环遇到的字符和第一个位置的字符交换，然后求剩下字符串的所有排列；对于剩下的字符串，重复前面的过程，所以这是个递归的过程，代码如下：
public class Solution {
private List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<List<Integer>> permute(int[] num) {
if(num == null || num.length == 0)
return result;
permutateArray(num, 0);
return result;
}
private void permutateArray(int[] num, int start){
if(start == num.length){
ArrayList<Integer> list = new ArrayList<Integer>();
for(int e : num){
list.add(e);
}
result.add(list);
return;
}
for(int i = start; i < num.length; i++){
swap(num, start, i);
permutateArray(num, start+1);
swap(num, start, i);
}
}
private void swap(int[] num, int i, int j){
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}2. 字符串排列问题（包含相同字符）
其实该问题与不包含相同字符的情况类似，只不过在上述交换字符的过程中，需要判断被交换的字符在该位置是否出现过，假如出现过，则进入下一轮循环；假如没有出现过，则交换字符；我们可以采用一个HashSet来记录在该位置出现过的字符集合，代码如下：
public class Solution {
public List<List<Integer>> permuteUnique(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(num == null || num.length == 0)
return result;
permutate(result, num, 0);
return result;
}
private void permutate(List<List<Integer>> result, int[] num, int index){
if(index == num.length){
List<Integer> list = new ArrayList<Integer>();
for(int e : num){
list.add(e);
}
result.add(list);
return;
}
HashSet<Integer> set = new HashSet<Integer>();
for(int i = index; i < num.length; i++){
if(!set.contains(num[i])){
set.add(num[i]);
swap(num, i, index);
permutate(result, num, index+1);
swap(num, i, index);
}
}
}
private void swap(int[] num, int i, int j){
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
}3. 字符串组合问题（k元子集）
对于包含n个字符的字符串，求出其所有包含k个字符的组合；我们可以从某个字符是否在组合当中这个角度切入这个问题，代码如下：
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> combList = new ArrayList<List<Integer>>();
List<Integer> comb = new ArrayList<Integer>();
if(n < k)
return combList;
comb(combList, comb, k, n, 1);
return combList;
}
public void comb(List<List<Integer>> combList, List<Integer> comb, int k, int n, int start){
if(comb.size() == k){
combList.add(new ArrayList<Integer>(comb));
return;
}
for(int i = start; i <= n; i++){
comb.add(i);
comb(combList, comb, k, n, i+1);
comb.remove(comb.size()-1);
}
}
}
4. 子集问题（元素不重复）
递推式解法：假如现在有个集合A，他的所有子集的集合是B，现在向A中加入一个元素a，得到集合A1，则A1的所有子集的集合为：空集+B+B中每个元素添加元素a后得到的集合，所以我们可以得到如下代码：
public class Solution {
public List<List<Integer>> subsets(int[] S) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(S == null || S.length == 0)
return result;
result.add(new ArrayList<Integer>());
Arrays.sort(S);
for(int i = 0; i < S.length; i++){
List<List<Integer>> copy = new ArrayList<List<Integer>>();
for(List<Integer> sub : result){
List<Integer> e = new ArrayList<Integer>(sub);
e.add(S[i]);
copy.add(e);
}
result.addAll(copy);
}
return result;
}
}递归解法：与上述求K元子集类似，即对于某个元素，分别求解它在子集和不在子集中的情况，代码如下：
public class Solution {
public List<List<Integer>> subsets(int[] S) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> subSet = new ArrayList<Integer>();
if(S == null || S.length == 0)
return result;
Arrays.sort(S);
sub(S, result, subSet, 0);
return result;
}
private void sub(int[] s, List<List<Integer>> result, List<Integer> subSet, int i){
if(i == s.length){
ArrayList<Integer> list = new ArrayList<Integer>(subSet);
result.add(list);
return;
}
sub(s, result, subSet, i+1);
subSet.add(s[i]);
sub(s, result, subSet, i+1);
subSet.remove((Integer)s[i]);
}
}
5. 子集问题（包含重复元素）
递推解法：
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(num == null || num.length == 0)
return result;
result.add(new ArrayList<Integer>());
int prev = Integer.MAX_VALUE;
Arrays.sort(num);
List<List<Integer>> copy = new ArrayList<List<Integer>>();
for(int i = 0; i < num.length; i++){
if(num[i] != prev){
copy = new ArrayList<List<Integer>>();
for(List<Integer> e : result){
List<Integer> list = new ArrayList<Integer>(e);
list.add(num[i]);
copy.add(list);
}
}else{
List<List<Integer>> copy1 = new ArrayList<List<Integer>>();
for(List<Integer> e : copy){
List<Integer> list = new ArrayList<Integer>(e);
list.add(num[i]);
copy1.add(list);
}
copy = copy1;
}
result.addAll(copy);
prev = num[i];
}
return result;
}
}递归解法：与上述不包含重复元素的类似，只不过加了判断，代码如下：
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> list = new ArrayList<Integer>();
if(num == null || num.length == 0)
return result;
Arrays.sort(num);
sub(num, result, list, 0);
return result;
}
private void sub(int[] num, List<List<Integer>> result, List<Integer> list, int i){
if(i == num.length){
if(!result.contains(list)){
result.add(new ArrayList<Integer>(list));
}
return;
}
sub(num, result, list, i+1);
list.add(num[i]);
sub(num, result, list, i+1);
list.remove((Integer)num[i]);
}
}LeetCode：https://oj.leetcode.com/problems/subsets-ii/
最后
以上就是任性唇彩为你收集整理的递归思想解决经典问题的全部内容，希望文章能够帮你解决递归思想解决经典问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复