回溯法实现全排序Ⅰ(回溯法算法)

  本篇文章为你整理了回溯法实现全排序Ⅰ(回溯法算法)的详细内容,包含有回溯法全排列原理 回溯法算法 回溯法怎么实现 回溯方法 回溯法实现全排序Ⅰ,希望能帮助你了解 回溯法实现全排序Ⅰ。

  给定一个不含重复数字的数组 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个元素的排列,可以:

  
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 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;

  

 

  以上代码转自力扣题解。笔者自己画图总结出来的解析。

  以上就是回溯法实现全排序Ⅰ(回溯法算法)的详细内容,想要了解更多 回溯法实现全排序Ⅰ的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: