Leetcode 46：permutations Leetcode 47: permutationsII

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

DFS解法： DFS 层数nums.size(); DFS每层的分支数nums.size()-cur
 在DFS解法中，将当前的char与当前层位置所在char进行交换，每次将char交换到每层的固定位置，通过这样的方式实现permutation。
 class Solution {
private:
    void DFS(vector<vector<int>> &rst, vector<int> nums, int cur) {
        //base case
        if (cur == nums.size()) {
            rst.push_back(nums);
            return;
        }
        for (int i = cur; i < nums.size(); i++) {
            swap(nums[i], nums[cur]);
            DFS(rst, nums, cur+1);
            swap(nums[i], nums[cur]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
         vector<vector<int>> rst;
         vector<int> solu;
        //sanity check
        if (nums.size() ==0) return rst;
        DFS(rst, nums, 0);
        return rst;
    }
};
PermutationII : with duplicates
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

本题是有duplicates， 做法与上面相同，只是在每一层进行处理的时候，用一个set记录当前层进行swap的char, 如果出现相同的char则跳过。 为了避免重复，在每一层中，不对相同的char进行处理。

class Solution {
private:
    void DFS(vector<vector<int>> &rst, vector<int> nums, int cur) {
        //base case
        if (cur == nums.size()) {
            rst.push_back(nums);
            return;
        }
        //use a set to deduplicate
        set<char> cset;
        for (int i = cur; i < nums.size(); i++) {
            if (cset.find(nums[i]) == cset.end()) {
                cset.insert(nums[i]);
                swap(nums[i], nums[cur]);
                DFS(rst, nums, cur+1);
                swap(nums[i], nums[cur]);
            }
        }
    }
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> rst;
        //sanity check
        if (nums.size() == 0) return rst;
        DFS(rst, nums, 0);
        return rst;
    }
};