I
Given a collection of numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
public class Solution { public ArrayList<ArrayList<Integer>> permute(int[] nums) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(nums==null||nums.length==0) return res; ArrayList<Integer> t = new ArrayList<Integer>(); t.add(nums[0]); res.add(t); for(int i=1;i<nums.length;i++){ res = helper(res, nums[i]); } return res; } private ArrayList<ArrayList<Integer>> helper(ArrayList<ArrayList<Integer>> res, int k){ ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); for(int i=0;i<res.size();i++){ for(int j=0;j<=res.get(i).size();j++){ ArrayList<Integer> t = new ArrayList<Integer>(res.get(i)); t.add(j,k); list.add(t); } } return list; } }
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].
题解：加个hashset 去掉duplicate即可
public class Solution { public ArrayList<ArrayList<Integer>> permuteUnique(int[] nums) { ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>(); if(nums==null||nums.length==0) return res; HashSet<ArrayList<Integer>> hs = new HashSet<ArrayList<Integer>>(); ArrayList<Integer> it = new ArrayList<Integer>(); it.add(nums[0]); res.add(it); for(int i=1;i<nums.length;i++){ res = helper(hs, res, nums[i]); } return res; } private ArrayList<ArrayList<Integer>> helper(HashSet<ArrayList<Integer>> hs,ArrayList<ArrayList<Integer>> res, int k){ ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>(); for(int i=0;i<res.size();i++){ for(int j=0;j<=res.get(i).size();j++){ ArrayList<Integer> t = new ArrayList<Integer>(res.get(i)); t.add(j,k); if(hs.contains(t)) continue; hs.add(t); r.add(t); } } return r; } }
原文：http://www.cnblogs.com/jiajiaxingxing/p/4545409.html