47. Permutations II

My solution modifies the input nums which costs a lot of performance (only beats 14%).

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> permuteUnique(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      vector<int> sol;  
6:      sort(nums.begin(), nums.end());  
7:      helper(nums, sol, res);  
8:      return res;  
9:    }  
10:    void helper(vector<int> &nums, vector<int> &sol, vector<vector<int>> &res) {  
11:      if (nums.size() == 0) {  
12:        res.push_back(sol);  
13:        return;  
14:      }  
15:      for (int i = 0; i < nums.size(); i++) {  
16:        if (i > 0 && nums[i] == nums[i-1]) continue;  
17:        int tmp = nums[i];  
18:        sol.push_back(nums[i]);  
19:        nums.erase(nums.begin()+i);  
20:        helper(nums, sol, res);  
21:        nums.insert(nums.begin()+i, tmp);  
22:        sol.pop_back();  
23:      }  
24:    }  
25:  };  

The top voted algorithm uses swap. Node it is not passing nums as reference as recursive calls keeps swapping the elements so nums[i] is changed by the following recursive calls and you can't simply play swap again to get it nums[i] back to its original position.

When I revisited this problem, I made a mistake in
Line 5: I forget sorting the array in first place.
Line 9: I pass in a reference and I swap back after line 17. However, this generate duplicates. For example, a = [1,1,2,2]. After you swap a[0] and a[2], you get a = [2,1,1,2] and then you’ll get subsequent permutation like [2,1,2,1]. However, if you swap back a[0] and a[2], and then you’ll swap a[0] and a[3], this time you’ll get [2,1,2,1] which is a duplicate. Then the question is why just one swapping works. Because it prevent you from swapping the same number again since you have check “i != start && nums[start] == nums[i]”.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> permuteUnique(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      sort(nums.begin(), nums.end());  
6:      helper(nums, 0, res);  
7:      return res;  
8:    }  
9:    void helper(vector<int> nums, int start, vector<vector<int>> &res) {  
10:      if (start == nums.size()) {  
11:        res.push_back(nums);  
12:        return;  
13:      }  
14:      for (int i = start; i < nums.size(); i++) {  
15:        if (i > start && nums[start] == nums[i]) continue;  
16:        swap(nums[start], nums[i]);  
17:        helper(nums, start+1, res);  
18:      }  
19:    }  
20:  };