LeetCode_回溯_中等_46.全排列

痛定思痛。 2023-10-06 18:57 61阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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中的所有整数互不相同

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/permutations

## 2.思路 ##

（1）回溯算法  
思路参考[回溯算法详解（修订版）][Link 1]。

（2）递归  
设 nums = \{r1,r2,…,rn\} 是要进行排列的 n 个元素，numsi=nums-\{ri\}。X中元素的全排列记为 Permutation(X)。(ri)Permutation(X) 表示在全排列 Permutation(X) 的每个排列前加上前缀 ri 得到的排列。所以 Permutation 的全排列可归纳定义如下：

*  当 n = 1 时，Permutation(nums) = ( r )，其中 r 是 nums 中的唯一元素；
 *  当 n > 1 时，Permutation(nums) 由 (r1)Permutation(nums1)，(r2)Permutation(nums2)，…，(rn)Permutation(numsn) 构成。

依此递归定义，可以设计产生下面的递归算法。

相关题目：  
[LeetCode\_回溯\_BFS\_中等\_784.字母大小写全排列][LeetCode_BFS_784.]

## 3.代码实现（Java） ##

//思路1————回溯算法
    class Solution {
        
    
        // res 用于保存最终结果
        List<List<Integer>> res = new LinkedList<>();
        // track 用于记录回溯的路径
        List<Integer> track = new ArrayList<>();
        
        public List<List<Integer>> permute(int[] nums) {
        
            backtrack(nums);
            return res;
        }
        
        public void backtrack(int[] nums) {
        
            if (track.size() == nums.length) {
        
                res.add(new ArrayList<>(track));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
        
                //去掉元素重复出现的情况
                if (track.contains(nums[i])) {
        
                    continue;
                }
                //做选择
                track.add(nums[i]);
                //进入下一层决策树
                backtrack(nums);
                //撤销选择
                track.remove(track.size() - 1);
            }
        }
    }

//思路2————递归
    class Solution {
        
    
        List<List<Integer>> res = new ArrayList<>();
    
        public List<List<Integer>> permute(int[] nums) {
        
            int length = nums.length;
            List<Integer> listNums = new ArrayList<>();
            for (int num : nums) {
        
                listNums.add(num);
            }
            permutation(listNums, 0, length - 1);
            return res;
        }
    
        //产生 nums[k:m] 的所有排列
        public void permutation(List<Integer> listNums, int k, int m) {
        
            //只剩下一个元素
            if (k == m) {
        
                res.add(new ArrayList<>(listNums));
            } else {
        
                for (int i = k; i <= m; i++) {
        
                    Collections.swap(listNums, k, i);
                    permutation(listNums, k + 1, m);
                    Collections.swap(listNums, k, i);
                }
            }
        }
    }

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484709&idx=1&sn=1c24a5c41a5a255000532e83f38f2ce4&chksm=9bd7fb2daca0723be888b30345e2c5e64649fc31a00b05c27a0843f349e2dd9363338d0dac61&scene=178&cur_album_id=2122002916411604996#rd
[LeetCode_BFS_784.]: https://blog.csdn.net/weixin_43004044/article/details/127595881