Permutations I&&II

Permutations I

Given a collection of distinct 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].

这里需要特别注意，第15行用的是index+1,而不是i+1这里也是与以前的代码思路不一样的地方，开始就是这里用了i+1,导致测试一直不通过，试了很久才发现这个错误。

class Solution {
 private:
     vector<vector<int>> res;
 public:
     void getPer(vector<int>&nums,int index,int lenth)
     {
         if(index==lenth)
             res.push_back(nums);
         int temp;
         for(int i=index;i<lenth;i++)
         {
             temp=nums[i];
             nums[i]=nums[index];
             nums[index]=temp;
             getPer(nums,index+1,lenth);
             temp= nums[i];
             nums[i]=nums[index];
             nums[index]=temp;
         }
         return ;
     }
     vector<vector<int>> permute(vector<int>& nums) {
         getPer(nums,0,nums.size());
         return res;
         
    }
 };

Permutations II

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].

这道题其实也纠结了我很久。没想到只需要定义一个set来存储已经交换过的元素值就可以把问题完美的解决了。

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        if(num.size() <= 0) return res;
        permCore(num, 0);
        return res;
    }
private:
    vector<vector<int> > res;
    void permCore(vector<int> &num, int st){
        if(st == num.size()) res.push_back(num);
        else{
            set<int> swp;
            for(int i = st; i < num.size(); ++i){
                if(swp.find(num[i]) != swp.end()) continue;
                swp.insert(num[i]);
                swap(num, st, i);
                permCore(num, st+1);
                swap(num, st, i);
            }
        }
    }
    
    void swap(vector<int> &num, int left, int right){
        int tmp = num[left];
        num[left] = num[right];
        num[right] = tmp;
    }
};