A easy C++ solution using recursive, with explanation(23ms)


  • 1
    N

    Find all permutations without duplicates, we just need swap nums[start] and nums[i] if there are no elements in [start, i] equals to nums[i].

    If the vector nums is [1,2,1] .When begin = 0, i = 1, swap them, we get [2,1,1]. When begin = 1, i = 2, swap them, we get [1,1,2].

    The model of recursive call is:

    the number in the parentheses getPer(begin) denotes the value of begin.

    getPer(0):

    • i = 0 , getPer(1)
    • i = 1, getPer(2)
    • i = 2, getPer(3)

    getPer(1):

    • i=1,getPer(2)
    • i=2,getPer(3)

    getper(2):

    • i=2, getPer(3)

    Finally, the code is :

    class Solution {
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {
            vector<vector<int>> ans;
            getPer(ans, nums, 0);
            return ans;
        }
    private:
        bool isDup(vector<int>& nums, int i, int j)
        {
            for (int k = i; k < j; ++k)
                if (nums[k] == nums[j])
                    return true;
            return false;
        }
        
        void getPer(vector<vector<int>>& ans, vector<int>& nums, int start)
        {
            if (start >= nums.size() - 1)
            {
                ans.push_back(nums);
                return;
            }
            for (int i = start; i < nums.size(); ++i)
            {
                if (!isDup(nums, start, i))
                {
                    swap(nums[i], nums[start]);
                    getPer(ans, nums, start + 1);
                    swap(nums[i], nums[start]);
                }
            }
        }
    };
    

    Since there is no elements behind nums[num.size() - 1], the function getPer() just return when start = nums.size() - 1.

    Hope it helps.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.