Leetcode 47. 全排列 II（Java实现）

素颜马尾好姑娘i 2022-10-12 12:17 197阅读 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 中的所有整数 互不相同

#### 思路 ####

回溯+剪枝，先排序，因为排序可以让重复的元素在一块，剪枝的条件在于**前一个元素和当前元素是相同的，且未被使用过。**  
而既然“前一个元素和当前元素是相同的”，那就隐含条件index是大于0的。

因为**如果前一个重复元素没有使用过，那么在当前重复元素下一层的可选项中一定会存在，那么就会出现结果重复的现象。**

#### Java实现 ####

class Solution {
        
        private boolean[] visit = new boolean[100];
        private List<List<Integer>> result = new ArrayList<>();
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            Arrays.sort(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(i>0 && nums[i]==nums[i-1] && visit[i-1]==false)
                {
        
                    continue;
                }
                // 已经出现过的数字
                if (visit[i] == false) {
        
                    output.add(nums[i]);
                    visit[i] = true;
                    backTrackGetPermuteArray(cur + 1, output, nums);
    
                    output.remove(output.size() - 1);
                    visit[i] = false;
                }
            }
    
        }
    }