回溯法搜索排列树的算法框架（回溯法实现全排序Ⅰ）

给定一个不含重复数字的数组 nums   
  
  
  
  
  
  
  
 ，返回其 所有可能的全排列   
  
  
  
  
  
  
  
 。你可以 按任意顺序 返回答案 
  
  
  
  
  
  
  
 。

示例 1： 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 输入：nums = [0,1] 输出：[[0,1],[1,0]] 示例 3： 输入：nums = [1] 输出：[[1]]

存放于数组A的n个元素 
  
  
  
  
  
  
  
 ，生成其排列：

第一个元素不动


 


 


 


 


 


 


 


 
，生成后面n-1个元素的排列； 第一                、第二个元素互换 
 
 
 
 
 
 
 
，生成后面n-1个元素的排列； 最后  
   
   
   
   
   
   
   
  ，第一个 
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  、第n个元素互换

 

 

 

 

 

 

 

 
，生成后面n-1个元素的排列

为生成后面n-1个元素的排列
 

 

 

 

 

 

 

 
，继续采取下面的步骤：

第二个元素不动                 ，生成后面n-2个元素的排列； 第二















、第三个元素互换
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
，生成后面n-2个元素的排列； 最后















，第二个
  
  
  
  
  
  
  
  
、第n个元素互换                         ，生成后面n-2个元素的排列；

当排列的前n-2个元素已确定后
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
，为生成后面2个元素的排列























，可以：

第n-1个元素不动                 ，生成后面1个元素的排列
 
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  
，此时















，n个元素已构成排列；

第n-1 
  
  
  
  
  
  
  
 、第n个元素互换  
  
  
  
  
  
  
  
 ，生成后面1个元素的排列 
  
  
  
  
  
  
  
 ，此时


 


 


 


 


 


 


 


 
，n个元素已构成排列；

Java代码 class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); List<Integer> output = new ArrayList<Integer>(); for (int num : nums) { output.add(num); } int n = nums.length; backtrack(n, output, res, 0); return res; } public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) { // 所有数都填完了 if (first == n) { res.add(new ArrayList<Integer>(output)); } for (int i = first; i < n; i++) { // 动态维护数组 Collections.swap(output, first, i); // 继续递归填下一个数 backtrack(n, output, res, first + 1); // 撤销操作 Collections.swap(output, first, i); } } }

注:

(1)以下是java.util.Collections.swap()方法的声明


 


 


 


 


 


 


 


 
。

public static void swap(List<?> list,int i,int j) 参数 ​ list-- 在该列表中的调剂元素 
 
 
 
 
 
 
 
。 ​ i-- 要交换的一个元素的索引  
   
   
   
   
   
   
   
  。 ​ j-- 要交换的其它元素的索引

 

 

 

 

 

 

 

 
。

(2)

软件维护主要是指根据需求变化或硬件环境的变化对应用程序进行部分或全部的修改

C++代码 class Solution { public: void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){ // 所有数都填完了 if (first == len) { res.emplace_back(output); return; } for (int i = first; i < len; ++i) { // 动态维护数组 swap(output[i], output[first]); // 继续递归填下一个数 backtrack(res, output, first + 1, len); // 撤销操作 swap(output[i], output[first]); } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int> > res; backtrack(res, nums, 0, (int)nums.size()); return res; } };

以上代码转自力扣题解
 

 

 

 

 

 

 

 
。笔者自己画图总结出来的解析                 。