博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode 47 全排列
阅读量:732 次
发布时间:2019-03-21

本文共 926 字,大约阅读时间需要 3 分钟。

  • 分析
    这道题要比46题要难,主要难在nums可能会有重复的数字,因为有重复的数字,所以为了标识哪个数字被选择可以用一个bool数组来记录一下,在做选择和撤销选择的时候需要同步,需要注意的是for循环里面做选择的条件,画出决策树之后就很好理解了。
  • 代码
class Solution {
public: vector
> vec; vector
> permuteUnique(vector
& nums) {
//排序 sort(nums.begin(), nums.end()); vector
road; vector
judge(nums.size(), false); backtrack(nums, road, judge); return vec; } void backtrack(vector
& nums, vector
& road, vector
& judge){ //结束条件 if(road.size() == nums.size()){ vec.push_back(road); return; } for(int i = 0; i < nums.size(); i++){ int data = nums[i]; //做选择的条件 if(judge[i] || (i > 0 && nums[i] == nums[i - 1] && !judge[i - 1])) continue; //做选择 judge[i] = true; road.push_back(data); //遍历下一层 backtrack(nums, road, judge); //撤销节点 road.pop_back(); judge[i] = false; } } };

转载地址:http://vnqgz.baihongyu.com/

你可能感兴趣的文章