class Solution {
public:
void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
if (i == j1) {
res.push_back(num);
return;
}
for (int k = i; k < j; k++) {
if (i != k && num[i] == num[k]) continue;
swap(num[i], num[k]);
recursion(num, i+1, j, res);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> >res;
recursion(num, 0, num.size(), res);
return res;
}
};
A simple C++ solution in only 20 lines


First, note that any modification to the loop change the behavior of the loop. If you swap it back, the algorithm completely changes. It is not a straight forward algorithm. Try write down "12345" and simulate on paper to see how it changes. You will notice the difference between "swap them back" and "not swap them back".
That also answers why we cannot use reference(because we cannot swap everything back in each recursion level.)

Thanks for your response. Yes, I understand that any modification to the loop change the behavior of the loop. I think both of the following ways work: 1, use reference and swapping back, 2, no reference and no swapping back. I have checked and verified that both work for "12345" and also for "112345". Unfortunately, the method of "using reference and swapping back" caused "Output Limit Exceeded" in OJ. It is a mystery to me why it fails, though the logic is very clear and clean. The following is the code, just a little change from guoang's:
class Solution {
public:
void recursion(vector<int>& num, int i, vector<vector<int> > &res) { if (i == num.size()1) { res.push_back(num); return; } for (int k = i; k < num.size(); k++) { if (i != k && num[i] == num[k]) continue; swap(num[i], num[k]); recursion(num, i+1, res); swap(num[i], num[k]); } } vector<vector<int> > permuteUnique(vector<int> &num) { sort(num.begin(), num.end()); vector<vector<int> >res; recursion(num, 0, res); return res; }
};

You are outputing a lot of duplicate solutions if there is something like "1112345". guoang's solution is following strictly the "next permutation" order. If you swap it back, you are not following that order, which result in a lot of duplicate solutions. Google "next permutation" if you don't know what it is.

Nice code! I take quite a long time to understand this. In each loop, the num[i+1:] can keep its order as well. That's real interesting!
And a improvement to reduce the space complexity on the parameter num
class Solution { public: vector<vector<int> > resList; vector<vector<int>> permute(vector<int>& nums) { sort(nums.begin(), nums.end()); dfs(0, nums); return resList; } void dfs(int i, vector<int>& nums){ if (i >= nums.size()){ resList.push_back(nums); return; } int p; for (p = i; p < nums.size(); p++){ if (p > i && nums[p] == nums[i]) continue; swap(nums[i], nums[p]); dfs(i + 1, nums); } int last = nums[i]; for (p = i + 1;p < nums.size(); p++) nums[p  1] = nums[p]; nums[p  1] = last; } };

Here is the working Java version I wrote:
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); Arrays.sort(nums); permutating(ans, nums, 0); return ans; } private void permutating(List<List<Integer>> ans, int[] nums, int start) { if (start == nums.length) { List<Integer> li = new ArrayList<>(); for (int n : nums) { li.add(n); } ans.add(li); return; } for (int i = start; i < nums.length; i++) { if (i != start && nums[start] == nums[i]) { continue; } swap(nums, start, i); permutating(ans, Arrays.copyOf(nums, nums.length), start+1); } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

The key to make the following duplicate control statement work is to use "pass by values" of nums array to the next level of recursion:
if (i != start && nums[start] == nums[i]) {
continue;
}As people discussed earlier in the thread, "pass by value" has totally different recursion sequence from "pass by reference". "pass by reference " won't work in this algorithm. Java doesn't have pass by value syntax for array(neither C#), so I pass a copy to preserve the original array.

Nice solution. Rewriting it in C# below:
public IList<IList<int>> PermuteUnique(int[] nums) { IList<IList<int>> result = new List<IList<int>>(); Array.Sort(nums); dfs(result, nums, 0); return result; } private void dfs(IList<IList<int>> result, int[] nums, int iCur){ if(iCur == nums.Length  1) result.Add(new List<int>(nums)); else for(int i = iCur; i < nums.Length; i++){ if(i != iCur && nums[iCur] == nums[i]) continue; int[] newNums = new int[nums.Length]; nums[iCur] = nums[iCur] ^ nums[i] ^ (nums[i] = nums[iCur]); Array.Copy(nums, newNums, nums.Length); dfs(result, newNums, iCur + 1); } }

Basically your idea is sorting first and then applying same method for permutation I. Here is my code which is similar except I use reference for num in the helper function, why did I get TLE on [3,3,0,0,2,3,2]. Could anyone give me a hint???
class Solution { public: void helper(vector<vector<int>>& res, int pos, vector<int>& nums)//0...pos1 already permutated { if(pos == nums.size()) { res.push_back(nums); return; } for(int i = pos; i < nums.size(); ++i) { if(i != pos && nums[i] == nums[pos]) continue; swap(nums[i], nums[pos]); helper(res, pos + 1, nums); swap(nums[i], nums[pos]); } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; if(nums.empty())return res; sort(nums.begin(), nums.end()); helper(res, 0, nums); return res; }
};