给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
2、算法分析3、代码实现首先这是一个回溯算法的经典排序题目。注意题目中说的是序列中的元素是重复的。
回溯算法是基于递归的,而在回溯算法中N叉树的递归思想很重要。尤其是子结点向父节点回溯。
首先看下回溯算法的解题模板:
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 } }这个题目是排序的,同层元素中需要剪枝
①定义结果集List,和每个符合条件的path
②回溯函数有两个参数,数组nums,判断数组中的元素搜否出现过的used boolean数组
③判空条件依然是path.size() == nums.length;说明找到一组符合条件的,将path添加到结果集合中
④最最重要的是下面的去重,因为排列的话比如1,2,1,其中的两个1在1,2,1这种情况下是只计一种的。
因为nums数组是进行排序的,所以比较相邻元素是否相等。
used[i - 1] == false,说明同一树层的元素nums[i-1]没有出现过。这个比较重要。
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){ continue; }if (used[i] == false) { used[i] = true;//标记同⼀树⽀nums[i]使⽤过,防止同一树支重复使用 path.add(nums[i]); backTrack(nums, used); path.remove(path.size() - 1);//回溯,说明同⼀树层nums[i]使⽤过,防止下一树层重复 used[i] = false;//回溯 }好,下面看代码:
class Solution { List> result = new ArrayList<>(); List
path = new ArrayList<>(); public List > permuteUnique(int[] nums) { boolean[] used = new boolean[nums.length]; Arrays.sort(nums); backTracking(nums,used); return result; } public void backTracking(int[] nums,boolean[] used){ if(path.size() == nums.length){ result.add(new ArrayList<>(path)); } for(int i = 0;i < nums.length;i++){ // 结束条件,去同层相同元素,因为是排序 if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){ continue; } if(used[i] == false){ // 表示同一树枝的nums[i]这个元素已经使用过 used[i] = true; // 添加到路径里面 path.add(nums[i]); // 递归 backTracking(nums,used); // 子结点回溯到父节点中,继续搜索 path.remove(path.size() - 1); // 因为是排序,以后的元素也要使用,所以used[i] == false; used[i] = false; } } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)