做临时工看哪个网站/网络软文发布

比起http://blog.csdn.net/fightforyourdream/article/details/14217105

多加了一个while来去重，发现这个去重方法在另一道题也用过，同样也是DFS里面去重，很好用！

另外就是在最前面加了一个sort，因为如果没加，当输入乱序时就会Output Limit Exceed!

package Level4;import java.util.ArrayList;
import java.util.Collections;/*** Permutations II * * Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].**/
public class S47 {public static void main(String[] args) {int[] num = {1,2,1};System.out.println(permuteUnique(num));}public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();ArrayList<Integer> done = new ArrayList<Integer>();ArrayList<Integer> rest = new ArrayList<Integer>();for(int val : num){rest.add(val);}Collections.sort(rest);		// 这里要先排序一下。。否则遇到非递增排序的输入就会Output Limit Exceed!rec2(done, rest, ret);return ret;}public static void rec2(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret){if(rest.size() == 0){ret.add(new ArrayList<Integer>(done));return;}for(int i=0; i<rest.size(); i++){done.add(rest.get(i));ArrayList<Integer> newRest = new ArrayList<Integer>(rest);newRest.remove(i);rec2(done, newRest, ret);done.remove(done.size()-1);while(i<rest.size()-1 && rest.get(i)==rest.get(i+1)){i++;}}}
}

过滤重复元素方法同http://blog.csdn.net/fightforyourdream/article/details/16859111

public class Solution {public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();ArrayList<Integer> done = new ArrayList<Integer>();ArrayList<Integer> rest = new ArrayList<Integer>();Arrays.sort(num);for(int val : num){rest.add(val);}rec(done, rest, ret);return ret;}public void rec(ArrayList<Integer> done, ArrayList<Integer> rest, ArrayList<ArrayList<Integer>> ret){if(rest.size()==0){ret.add(new ArrayList<Integer>(done));return;}for(int i=0; i<rest.size(); i++){int first = rest.remove(i);done.add(first);rec(done, rest, ret);done.remove(done.size()-1);rest.add(i, first);     // insert to its original positionwhile(i+1<rest.size() && rest.get(i)==rest.get(i+1)){i++;}}}
}