Easiest C++ backtracking solution without map or sort (with none-recursive version) (23ms)


  • 0
    S
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, result, vector<int>(), 0);
        return result;
    }
    void backtrack(vector<int> &nums, vector<vector<int>> &result, vector<int> permutation, int index) {
        if (index == nums.size()) {
            result.push_back(permutation);
            return;
        }
        
        for (int i = 0; i <= permutation.size(); i++) {
            // Don't insert after the same value to skip duplicates
            if (i > 0 && permutation[i - 1] == nums[index])
                break;
            permutation.insert(permutation.begin() + i, nums[index]);
            backtrack(nums, result, permutation, index + 1);
            permutation.erase(permutation.begin() + i);
        }
    }
    

    A none-recursive version with the same idea

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result = {{}};
        for (int n : nums) {
            vector<vector<int>> tmp;
            for (vector<int> v : result) {
                for (int i = 0; i <= v.size(); i++) {
                    if (i > 0 && v[i - 1] == n)
                        break;
                    v.insert(v.begin() + i, n);
                    tmp.push_back(v);
                    v.erase(v.begin() + i);
                }
            }
            result= tmp;
        }
        return result;
    }
    

Log in to reply
 

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