力扣——全排列

骑猪看日落 2023-10-02 11:42 29阅读 0赞

##### [全排列][Link 1] #####

> 给定一个不含重复数字的数组 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\]\]

提示：

> 1 <= nums.length <= 6  
> \-10 <= nums\[i\] <= 10  
> nums 中的所有整数 互不相同

--------------------

class Solution {
        
        public List<List<Integer>> permute(int[] nums) {
        
        ArrayList<List<Integer>> res = new ArrayList<>();
    
            ArrayList<Integer> output = new ArrayList<>();
            for (int num:nums){
        
                //遍历数组中的每一个元素，并存入output中
                output.add(num);
            }
    
            int n=nums.length;
            backtrack(n,output,res,0);
            return res;
        }
    
     public  void backtrack(int n,ArrayList<Integer> output,ArrayList<List<Integer>> res,int first){
        
            //所有数都填完
            if(first==n){
        
                res.add(new ArrayList<Integer>(output));//将output中的元素存给res
            }
            for (int i = first; i < n; i++) {
        
                //动态维护数组
                Collections.swap(output,first,i);
                //继续递归填下一个数
                backtrack(n,output,res,first+1);
                //撤销操作
                Collections.swap(output,first,i);
            }
        }
    
    }

--------------------

实现调用：

package com.kk;
    
    import java.util.*;
    
    //全排列
    public class Permute {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int[] nums = new int[3];
            for (int i = 0; i < nums.length; i++) {
        
                nums[i]=scanner.nextInt();
            }
            List<List<Integer>> permute = permute(nums);
            System.out.println(Arrays.toString(new List[]{
        permute}));
    
        }
    
        public static List<List<Integer>> permute(int[] nums) {
        
            ArrayList<List<Integer>> res = new ArrayList<>();
    
            ArrayList<Integer> output = new ArrayList<>();
            for (int num:nums){
        
                //遍历数组中的每一个元素，并存入output中
                output.add(num);
            }
    
            int n=nums.length;
            backtrack(n,output,res,0);
            return res;
        }
    
        public static void backtrack(int n,ArrayList<Integer> output,ArrayList<List<Integer>> res,int first){
        
            //所有数都填完
            if(first==n){
        
                res.add(new ArrayList<Integer>(output));//将output中的元素存给res
            }
            for (int i = first; i < n; i++) {
        
                //动态维护数组
                Collections.swap(output,first,i);
                //继续递归填下一个数
                backtrack(n,output,res,first+1);
                //撤销操作
                Collections.swap(output,first,i);
            }
        }
    }
    
    //Collections.swap使用用法
    //https://www.it610.com/article/5478747.html
     /*
         Collections.swap(output,first,i);
                output-- 在该列表中的调剂元素。
    
                first-- 要交换的一个元素的索引。
    
                i-- 要交换的其它元素的索引。
    */

[Collections.swap使用用法][Collections.swap]

[Link 1]: https://leetcode-cn.com/problems/permutations/
[Collections.swap]: https://www.it610.com/article/5478747.html