adnanaziz/epicode

Simpler alternative for permutations-unique.cc

Opened this issue · 0 comments

@adnanaziz @thlee-uber - I am not sure if this is the right avenue to bring this to your attention. I apologize in advance if that is indeed not the case.

This is a slight modification to the approach in permutations-alternative.cc:

    vector<vector<int>> permute_unique(vector<int> nums)
    {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        permute_unique_recursive(0, &nums, &result);
        return result;
    }
    void permute_unique_recursive(int index_start, vector<int>* arr, vector<vector<int>>* result)
    {
        vector<int>& a = *arr;
        if (index_start == arr->size() - 1) {
            result->emplace_back(a);
            return;
        }
        permute_unique_recursive(index_start + 1, arr, result);
        for (int i = index_start + 1, n = arr->size(); i < n; ++i) {
            if (a[index_start] == a[i])
                continue;
            swap(a[index_start], a[i]);
            permute_unique_recursive(index_start + 1, arr, result);
        }
        rotate(a.begin() + index_start, a.begin() + index_start + 1, a.end());
    }