全排列I/II

题目：https://leetcode-cn.com/problems/permutations/ 题目2：https://leetcode-cn.com/problems/permutations-ii/

全排列

class Solution {
public:
    void dfs(int id) {
        if(id == n) {
            ans.push_back(res);
            return;
        }
        for(int i = id;i res = nums;
        n = nums.size();
        dfs(0);
        return ans;
    }
private:
    vector ans;
    vector res;
    int n;
};

全排列II

在全排列I基础上，比较耗空间

class Solution {
public:
    /*
    *给定一个可包含重复数字的序列，返回所有不重复的全排列。
    */
    void dfs(int id) {
        if(id == n) {
            ans.push_back(res);
            return;
        }
        unordered_map vis;
        for(int i = id;i res = nums;
        dfs(0);
        return ans;
    }
private:
    vector ans;
    vector res;
    int n;
};

解法2，减少空间开销，耗时间

class Solution {
public:
    /*
    *给定一个可包含重复数字的序列，返回所有不重复的全排列。
    */
    void dfs(int id) {
        if(id == n) {
            ans.push_back(res);
            return;
        }
        for(int i = 0;i  0 && nums[i] == nums[i-1] && !vis[i-1]) //防重复 
				continue;
            vis[i] = true;
            res.push_back(nums[i]);
            dfs(id+1);
            res.pop_back();
            vis[i] = false;
        }
    }
    vector permuteUnique(vector& nums) {
        n = nums.size();
        sort(nums.begin(),nums.end());
        this->nums = nums;
        vis.clear();
        dfs(0);
        return ans;
    }
private:
    vector ans;
    vector res,nums;
    int n;
    unordered_map vis;
};