[Leetcode 47][Medium]-全排列 II-回溯(全排列问题)

目录

一、题目描述

二、整体思路

三、代码

---

一、题目描述

原题地址

二、整体思路

        和上一道Leetcode46相比，有变化的地方是要排除重复组合的情况。那么在组合问题中去除重复组合的方法是先对数组进行排序,然后在回溯函数中判断当前元素与上一个元素是否相同,若相同则直接访问下一个元素。在全排列问题中要稍微改一下。

        以{1,1,2}为例

三、代码

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> temp=new ArrayList<>();public List<List<Integer>> permuteUnique(int[] nums) {boolean[] visited=new boolean[nums.length];Arrays.sort(nums);backtrace(visited,nums);return res;}void backtrace(boolean[] visited,int[] nums){if(temp.size()==nums.length){res.add(new ArrayList<>(temp));}for(int i=0;i<nums.length;i++){if(i>0 && visited[i-1]!=true && nums[i]==nums[i-1]){continue;}if(visited[i]){continue;}temp.add(nums[i]);visited[i]=true;backtrace(visited,nums);visited[i]=false;temp.remove(temp.size()-1);}}
}