Exercises IV

medium 2

Permutation

medium

原题链接

解法：DFS全排列

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        permutation(nums,0,res);
        return res;
    }
    void permutation(vector<int>& nums, int n, vector<vector<int>> &res){
        if(n==nums.size()-1){
            res.push_back(nums);
        }else{
            for(int i=n; i<nums.size(); i++){
                swap(nums[i],nums[n]);
                permutation(nums,n+1,res);
                swap(nums[i],nums[n]);
            }   
        }
    }
};

swap back only for pass by reference

Permutations II

medium

原题链接

解法：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>res;
        permutation(nums,0,res);
        return res;
    }
    void permutation(vector<int> nums, int n, vector<vector<int>> &res){
        if(n==nums.size()-1){
            res.push_back(nums);
        }else{
            for(int i=n; i<nums.size(); i++){
                if(i!=n&&nums[i]==nums[n]){continue;}
                    swap(nums[i],nums[n]);
                    permutation(nums,n+1,res);
                   // swap(nums[i],nums[n]);
            }
        }
    }
};