leetcode 47 全排列II

我不是女神ヾ 2022-09-14 09:12 157阅读 0赞

## 题目 ##

题目：[47. 全排列 II][47. _ II]

参考题解：[47.全排列 II-代码随想录][47._ II-]

--------------------

## 提交代码 ##

比较简单，在[leetcode 46 全排列][leetcode 46]的基础上，保证同一层不要取相同元素即可。

参考题解没有使用辅助空间。我瞅了瞅，没看懂。可自行阅读参考题解的实现。

#include <vector>
    #include <iostream>
    #include <algorithm>
    #include <set>
    
    using namespace std;
    
    class Solution {
    public:
        void backTracking(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result){
            if(path.size() == nums.size()){
                result.push_back(path);
                return;
            }
    
            set<int> level_prev; // 同一层，不可以出现重复
            for(int i=0; i<nums.size(); i++){
                if(used[i] || level_prev.count(nums[i])) // 纵向上，选择新节点时，使用过的不可再选；横向上，同一层不可有相同的元素
                    continue;
                used[i] = true;
                level_prev.insert(nums[i]);
                path.push_back(nums[i]);
                backTracking(nums,used,path,result);
                path.pop_back();
                used[i] = false;
            }
            
        }
    
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            vector<bool> used(nums.size(),false);
            vector<int> path;
            vector<vector<int>> result;
            backTracking(nums,used,path,result);
            return result;
        }
    };
    
    
    int main(void){
        vector<int> nums = {1,2,1};
        Solution s;
        vector<vector<int>> result = s.permuteUnique(nums);
        for(auto one : result){
            for(auto num : one)
                cout<<num<<" ";
            cout<<endl;
        }
    }

[47. _ II]: https://leetcode-cn.com/problems/permutations-ii/
[47._ II-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0047.%E5%85%A8%E6%8E%92%E5%88%97II.md
[leetcode 46]: https://blog.csdn.net/sinat_38816924/article/details/120587564