这两个问题关联性很强就放到一起了

题目描述

46，Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

47，Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

算法实现：

采用递归的方式，将传入的数组在当前位置和其后的所有元素依次交换位置，交换后再依次递归后面的位置。对47题中可能出现的重复元素则不再交换

//46
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.empty()) return res;
        RE(nums, res, 0);
        return res;
    }
    void RE(vector<int>& nums,vector<vector<int>> &res,int s){
        if(s == nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i = s; i < nums.size(); i ++){
            swap(nums[i], nums[s]);
            RE(nums, res, s + 1);
            swap(nums[i], nums[s]);            
        }
        return;
    }
};

//47
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.empty()) return res;
        RE(nums, res, 0);
        return res;
    }
    void RE(vector<int>& nums,vector<vector<int>> &res,int s){
        if(s == nums.size()){
            res.push_back(nums);
            return;
        }
        for(int i = s; i < nums.size(); i ++){
            
            bool flag = false;
            //之前交换过的元素中如果出现重复的就无须再次交换
            for(int j = s; j < i; j ++)
                if(nums[i] == nums[j])
                {
                    flag = true;
                    continue;
                }
            if(flag)continue;
            swap(nums[i], nums[s]);
            RE(nums, res, s + 1);
            swap(nums[i], nums[s]);            
        }
        return;
    }
};