13 lines C++ backtracking


  • 0

    My solution for Permutations I.

    Solution for Permutations II is similar to Permutations I, the only difference is that we CAN'T swap back after each permutation, cause we want to pick a new different number for position i in each loop.

    For example, suppose array nums = [1, 1, 2, 2, 3], first we swap nums[0] = 1 with the first different number nums[2] = 2, after first swap, nums = [2, 1, 1, 2, 3], then if we swap back 1 with 2, nums = [1, 1, 2, 2, 3].

    Now, we want to pick nums[4] = 3 as a new number for position 0, but nums[3] = 2 would be considered the new different number because we swap the number '1' back to position 0, so we will swap nums[0] with nums[3], nums = [2, 1, 2, 1, 3], so the same number '2' appears twice at position 0, which cause the repeated outcomes.

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

Log in to reply
 

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