Java算法练习—递归/回溯

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能将原本的问题分解为更小的子问题，这是使用递归的关键。

如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。

1、BM55没有重复项数字的全排列

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数

要求：空间复杂度，时间复杂度

示例1

输入：

[1,2,3]

返回值：

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入：

[1]

返回值：

[[1]]

思路：

全排列就是对数组元素交换位置，使每一种排列都可能出现。因为题目要求按照字典序排列输出，那毫无疑问第一个排列就是数组的升序排列，它的字典序最小，后续每个元素与它后面的元素交换一次位置就是一种排列情况，但是如果要保持原来的位置不变，那就不应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变，不会漏情况。

如何保证每个元素能和从自己开始后的每个元素都交换位置，这种时候我们可以考虑递归。为什么可以使用递归？我们可以看数组[1,2,3,4]，如果遍历经过一个元素2以后，那就相当于我们确定了数组到该元素为止的前半部分，前半部分1和2的位置都不用变了，只需要对3，4进行排列，这对于后半部分而言同样是一个全排列，同样要对从每个元素开始往后交换位置，因此后面部分就是一个子问题。那我们考虑递归的几个条件：

• 终止条件：要交换位置的下标到了数组末尾，没有可交换的了，那这就构成了一个排列情况，可以加入输出数组。
• 返回值：每一级的子问题应该把什么东西传递给父问题呢，这个题中我们是交换数组元素位置，前面已经确定好位置的元素就是我们返还给父问题的结果，后续递归下去会逐渐把整个数组位置都确定，形成一种排列情况。
• 本级任务：每一级需要做的就是遍历从它开始的后续元素，每一级就与它交换一次位置。

如果只是使用递归，我们会发现，上例中的1与3交换位置以后，如果2再与4交换位置的时候，我们只能得到3412这种排列，无法得到1432这种情况。这是因为遍历的时候1与3交换位置在2与4交换位置前面，递归过程中就默认将后者看成了前者的子问题，但是其实我们1与3没有交换位置的情况都没有结束，相当于上述图示中只进行了第一个分支。因此我们用到了回溯。处理完1与3交换位置的子问题以后，我们再将其交换回原来的情况，相当于上述图示回到了父节点，那后续完整的情况交换我们也能得到。

//遍历后续的元素
for(int i = index; i 

具体做法：

• step 1：先将数组排序，获取字典序最小的排列情况。
• step 2：递归的时候根据当前下标，遍历后续的元素，交换二者位置后，进入下一层递归。
• step 3：处理完一分支的递归后，将交换的情况再换回来进行回溯，进入其他分支。
• step 4：当前下标到达数组末尾就是一种排列情况。

图示：

暴力递归 + 回溯(省空间)
每次递归, 从小到大(所以一上来要对num进行排序)遍历待选的数,
选到的数从remain中删除，并插入perm中。

import java.util.*;

public class Solution {
    ArrayList> ans = new ArrayList();
    
    public ArrayList> permute(int[] num) {
      // sort just to insure outp服务器托管网ut in alphabet order
      Arrays.sort(num);
      // copy sorted nums to remain
      ArrayList服务器托管网 remain = new ArrayList();
      for (int n : num) remain.add(n); 
      
      permuteRec(remain, new ArrayList());
      return ans;
    }
  
    public void permuteRec(ArrayList remain, ArrayList perm) {
      // base case, i.e. no remaining elem
      if (remain.isEmpty()) {
        // 存答案时必须存copy, 不然之后的回溯会overwrite存入的答案。
        ans.add(new ArrayList(perm));
        return;
      }
      
      for (int i = 0; i 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Java设计模式：一、六大设计原则-06：依赖倒置原则
一、定义：依赖倒置原则
二、模拟场景：依赖倒置原则
三、违背方案：依赖倒置原则
四、改善代码：依赖倒置原则

文章目录 一、定义：依赖倒置原则 二、模拟场景：依赖倒置原则 三、违背方案：依赖倒置原则 3.1 工程结构 3.2 抽奖系统 **3.2.1 定义抽奖用户类** 3.2.2 抽奖控制 3.3 单元测试 四、改善代码：依赖倒置原则 4.1 工程结构 4.2 抽奖…