I think this code not only have a TLE but also produce incorrect result. I have posted a similar solution with small modifications, which fixed the bug in this code. https://leetcode.com/discuss/38948/java-recursive-solution-without-extra-space

Here is the original code in this post with some additional debug System.out.printf method.

public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
s.permuteUnique(new int[] {1,2,3,1,2,1});
}
public List<List<Integer>> permuteUnique(int[] num) {
ArrayList<List<Integer>> rst = new ArrayList<List<Integer>>();
Arrays.sort(num);
getPermute(num, 0, rst); return rst;
}
public void getPermute(int[] num, int start, ArrayList<List<Integer>> rst){
if(start == num.length){
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i : num){ list.add(i); }
rst.add(list); return;
}
for(int i = start; i < num.length; i++){
if(i > start && num[i] == num[start]){
continue;
}
swap(num, i, start);
getPermute(num, start + 1, rst);
if ( start == 0 ) {
System.out.printf("i = %d, num = %s\n", i, Arrays.toString(num));
}
swap(num, i, start);
}
}
private void swap(int[] num, int i, int j){
int temp = num[i]; num[i] = num[j]; num[j] = temp;
}
}

Here are the messages that get printed out

i = 0, num = [1, 1, 1, 2, 2, 3] // remaining array = [1, 1, 2, 2, 3]
i = 3, num = [2, 1, 1, 1, 2, 3] // remaining array = [1, 1, 1, 2, 3]
i = 4, num = [2, 1, 1, 2, 1, 3] // remaining array = [1, 1, 2, 1, 3]
i = 5, num = [3, 1, 1, 2, 2, 1] // remaining array = [1, 1, 2, 2, 1]

In order to make this method work, we need to make sure when we recursive call getPermute on the remaining array, the remaining array should stay sorted. However, given the sorted result, that's not the case. Thus, this code not only have TLE but also produce incorrect answer.

There is a seemingly similar C++ answer to the code in this post by @guoang

class Solution {
public:
void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
if (i == j-1) {
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;
}
};

This code is correct because num is passed to method recursion as a copy, not a reference. In the Java code, the num is passed as a reference.