lintcode：全排列&带重复元素的排列

lintcode地址：

http://lintcode.com/zh-cn/problem/permutations/

http://lintcode.com/zh-cn/problem/permutations-ii/

全排列，用了子集树的解法：

class Solution {
public:
    /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
    int length;
    vector<int> num;
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int> &nums) {
        // write your code here
        length = nums.size();
        for(int i=0;i<length;i++){
            num.push_back(0);
        }
        backtrack(0,nums);
        return res;
    }
    
    bool isOk(int t){
        for(int i=0;i<=t;i++){
            for(int j=i+1;j<=t;j++){
                if(num[i] == num[j])
                    return false;
            }
        }
        return true;
    }
    
    void backtrack(int t,vector<int> &nums){
        if(t >= length){
            res.push_back(num);
            return;
        }
        
        for(int i=0;i<length;i++){
            num[t] = nums[i];
            if(isOk(t)){
                backtrack(t+1,nums);
            }
        }
    }
};

 

带重复元素的排列

筛选条件就是在i和t不等的时候，保证在t到i之间对应的排列数里没有和nums[i]重复的元素，就可以交换排列。

class Solution {
public:
    int length;
    vector<int> num;
    vector<vector<int>> res;
    /*
     * @param :  A list of integers
     * @return: A list of unique permutations
     */
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        // write your code here
        length = nums.size();
        sort(nums.begin(), nums.end());
        backtrack(0,nums);
        return res;
    }
    
    bool isOk(int i,int t,vector<int> &nums){
        if(i>t){
            for(int j=t;j<i;j++){
                if(nums[j]==nums[i])
                    return false;
            }
        }
        return true;
    }
    
    void backtrack(int t,vector<int> &nums){
        if(t >= length){
            res.push_back(nums);
            return;
        }
        
        for(int i=t;i<length;i++){
            if(isOk(i,t,nums)){
                swap(nums[i],nums[t]);
                backtrack(t+1,nums);
                swap(nums[i],nums[t]);
            }
        }
    }
};