Why this backtracking algorithm doesn't work


  • 1
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        permuteUniqueHelper(nums, 0, ret);
        return ret;
    }
    
    void permuteUniqueHelper(vector<int>& nums, int b, vector<vector<int>>& ret) {
        if (b == nums.size()) {
            ret.push_back(nums);
            return;
        }
        for (int i = b; i < nums.size(); i += 1) {
            if (i != b && (nums[i] == nums[b] || nums[i] == nums[i - 1])) continue;
            swap(nums[i], nums[b]);
            permuteUniqueHelper(nums, b + 1, ret);
            swap(nums[i], nums[b]);
        }
    }

  • 0
    C

    I want to know it too


  • 0

  • 0
    L

    some example, there are more than way to get 1551
    1[1]55 -> 1551
    1[1]55 -> 15[1]5 -> 1551


  • 0
    C

    I'm confused too. It seems that the order of these permutations in the answer must also be matched.


  • 0
    H

    Coz u swap nums[i] n nums[b] after recall permuteUniqueHelper.
    Then ur nums[i] will not change, but ur "if continue " can only make sure that the number with same value of nums[i] will not be considered again, which is means that, for 1,1,1,2,2,2,3,3,3, the value "1" will not repeat because nums[i] is 1, but all "2" n "3" will repeat because nums[i] is still "1", ur "if continue" doesn't work.


  • 1
    A

    Swaping causes the sort order to be disturbed hence failing the algorithms


  • 0
    L

    Assume at the beginning the subarray(b, end) is sorted, but once you swap nums[b] with another number in the middle of subarray(b, end), you break the order of the subarray, hence the "nums[i] == nums[i - 1]" check doesn't work as you expect, it's possible that nums[i + 1] == nums[i - 1] but nums[i] != nums[i - 1]


  • 0

    It's a math problem actually, solution is as follows which is my favourite.

    vector<vector<int>> permuteUnique(vector<int>& nums) 
        {
            sort(nums.begin(), nums.end());
            int size = nums.size(), i, j;
            vector<vector<int>> vv;
            while(true)
            {
                vv.push_back(nums);
                i = size-2, j = size-1;
                while(i>0 && nums[i]>=nums[i+1]) i--;
                while(j>0 && nums[i]>=nums[j]) j--;
                if(j == 0) break;
                swap(nums[i++], nums[j]);
                j = size-1;
                while(i<j)  swap(nums[i++], nums[j--]);     
            }
            return vv;
        }
    

Log in to reply
 

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