491. 递增子序列

因为数组不能排序，数字是乱序的，所以不能用和前面的比较来去重。使用 unordered_set 去重

class Solution {
public:
    // 不能排序  点和当前数组的最后一个比较 
    vector<vector<int>> res;
    vector<int> nums;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        this->nums = nums;
        vector<int> vec;
        dfs(vec, 0);
        return res;
    }

    void dfs(vector<int> &vec, int u)
    {
        if (vec.size() >= 2)
            res.push_back(vec);
        unordered_set<int> uset;  // 同一级不能有重复的
        for (int i = u; i < nums.size(); i ++)
        {
            if (i > u && uset.count(nums[i])) continue;
            if (vec.size() == 0 || vec[vec.size() - 1] <= nums[i])
            {
                uset.insert(nums[i]);
                vec.push_back(nums[i]);
                dfs(vec, i + 1);
                vec.pop_back();
            }
        }
    }
};

46. 全排列

class Solution {
public:
    vector<vector<int>> res;
    vector<int> nums;
    vector<bool> b;
    vector<vector<int>> permute(vector<int>& nums) {
        this->nums = nums;
        int n = nums.size();
        b.resize(n);
        vector<int> vec;
        dfs(vec);
        return res;
    }

    void dfs(vector<int>& vec)
    {
        if (vec.size() == nums.size())
        {
            res.push_back(vec);
            return;
        }
        for (int i = 0; i < nums.size(); i ++)
        {
            if (!b[i])
            {
                b[i] = true;
                vec.push_back(nums[i]);
                dfs(vec);
                vec.pop_back();
                b[i] = false;
            }
        }
    }
};

47. 全排列 II

剪枝有点意思 if (i > 0 && nums[i] == nums[i-1] && b[i-1] == false) continue;

false是在第一层就被剪枝 true是在最后一层被剪枝。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> nums;
    vector<bool> b;
    int n;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        this->nums = nums;
        n = nums.size();
        b.resize(n);
        vector<int> vec;
        dfs(vec);
        return res;
    }

    void dfs(vector<int> &vec)
    {
        if (vec.size() == n)
        {
            res.push_back(vec);
            return;
        }
        for (int i = 0; i < n; i ++)
        {
            if (i > 0 && nums[i] == nums[i-1] && b[i-1] == false) continue; //false是在第一层就被剪枝  true是在最后一层
            if (!b[i])
            {
                b[i] = true;
                vec.push_back(nums[i]);
                dfs(vec);
                vec.pop_back();
                b[i] = false;
            }
        }
    }
};