【算法题解】30. 全排列的递归解法

逃离我推掉我的手 2024-03-16 09:20 59阅读 0赞

> 这是一道 **中等难度** 的题  
>   
> https://leetcode.cn/problems/permutations/

### 题目 ###

给定一个不含重复数字的数组  n u m s nums 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 < = n u m s . l e n g t h < = 6 1 <= nums.length <= 6 1<=nums.length<=6
 *   − 10 < = n u m s \[ i \] < = 10 -10 <= nums\[i\] <= 10 −10<=nums\[i\]<=10
 *   n u m s nums nums 中的所有整数 **互不相同**

### 题解 ###

这道题还是 **递归** 的思路，以示例一  n u m s = \[ 1 , 2 , 3 \] nums = \[1,2,3\] nums=\[1,2,3\] 为例：

1.  递归函数：每次选取一个未曾选取过的元素，然后进入下一次递归。
2.  递归边界：当  n u m s nums nums 中的所有元素都被选完时，记录答案，并返回。
3.  还原现场：每次回退时（红色箭头）应该将本次选择的元素删除。

![a3c9a02b67b7a3abb01e7bbb5b8b5e7f.png][]

##### Java 代码实现 #####

class Solution {
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> selected = new ArrayList<>();
    
    
        public List<List<Integer>> permute(int[] nums) {
    
            recursion( nums);
            return ans;
        }
    
        private void recursion( int[] nums){
            int n = nums.length;
            // 边界条件
            if(selected.size() == n){
                ans.add(new ArrayList(selected));
                return;
            }
    
            for(int i = 0; i < n; i++){
                if(selected.contains(nums[i])){
                    continue;
                }
                selected.add(nums[i]);
                this.recursion( nums);
                selected.remove(selected.size() - 1);
            }
            
        }
    }

##### Go 代码实现 #####

var (
        ans [][]int
        selectedVal []int
        selectedIndex []bool
    )
    
    
    func permute(nums []int) [][]int {
        
        ans = make([][]int, 0)
        selectedVal = make([]int, 0)
        selectedIndex = make([]bool, len(nums))
    
        recursion(nums)
        return ans
    }
    
    func recursion(nums []int) {
        if len(selectedVal) == len(nums) {
            temp := make([]int, len(selectedVal))
            copy(temp, selectedVal)
            ans = append(ans, temp)
            return
        }
    
        for i, v :=  range nums{
            if selectedIndex[i]{
                continue
            }
    
            selectedIndex[i] = true
            selectedVal = append(selectedVal, v)
            recursion(nums)
            selectedIndex[i] = false;
            selectedVal = selectedVal[:len(selectedVal) - 1]
        }
    }

[a3c9a02b67b7a3abb01e7bbb5b8b5e7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/072295203e0c406486f516b3446af103.png