Leetcode 46. 全排列（Java实现）

本是古典何须时尚 2022-10-12 12:18 124阅读 0赞

#### 题目重述 ####

给定一个不含重复数字的数组 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 中的所有整数 互不相同

#### 思路 ####

把全排列看成是填数组的过程，之后用**回溯法**模拟填数组的过程，如果当前元素已经填过，那么设置visit数组标志已经填过，在填下个位置的时候，遍历需要全排列的数组，看哪个元素还没填。

终止条件是：已经填完。

#### Java实现 ####

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        
        private boolean[] visit = new boolean[100];
        private List<List<Integer>> result = new ArrayList<>();
    
        public List<List<Integer>> permute(int[] nums) {
        
            List<Integer> output = new ArrayList<>();
            backTrackGetPermuteArray(0,output,nums);
            return result;
        }
    
        /**
         * 回溯法
         * @param cur 当前填充的位置所在
         * @param output 已填充的数组
         * @param nums 需要全排列的数组
         */
        public void  backTrackGetPermuteArray(int cur,List<Integer> output,int[] nums)
        {
        
            if(cur == nums.length)
            {
        
                // 注意，所指向的列表 在深度优先遍历的过程中只有一份 ，深度优先遍历完成以后，回到了根结点，成为空列表。
                result.add(new ArrayList<>(output));
            }
            for (int i = 0; i < nums.length; i++) {
        
                // 已经出现过的数字
                if(visit[i] == false)
                {
        
                    output.add(nums[i]);
                    visit[i] = true;
                    backTrackGetPermuteArray(cur+1,output,nums);
    
                    output.remove(output.size()-1);
                    visit[i] = false;
                }
            }
    
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)