Leetcode:47. Permutations II

Description

Description

Given a collection of distinct numbers, return all possible permutations.

Example

For example,
[1,1,2] have the following unique permutations:

[
    [1,1,2],
    [1,2,1],
    [2,1,1]
]

思路

• 题一读完，感觉和46题可以使用同样的代码
• 一提交，AC，呵呵哒。。

代码

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
         vector<vector<int>> res;
        int len = nums.size();
        if(len == 0) return res;
        if(len == 1) {
            res.push_back(nums);
            return res;
        }
        
        sort(nums.begin(), nums.end());
        
        do{
            res.push_back(nums);
        }
        while(getNextPermute(nums, len));
        
        return res;    
    }
    
    bool getNextPermute(vector<int>& nums, int len){
        int index1 = 0, index2 = -1, flag = nums[0];
        for(int i = 1; i < len; ++i){
            if(nums[i] > nums[i - 1]){
                index1 = i - 1;
                index2 = i;
                flag = nums[i] - nums[i - 1];
            }
            else if(nums[i] > nums[index1] && nums[i] - nums[index1] < flag){
                index2 = i;
                flag = nums[i] - nums[index1];
            }
        }
        
        if(index2 == -1) return false;
        
        swap(nums[index1], nums[index2]);
        sort(nums.begin() + index1 + 1, nums.end());
        return true;
    }
};