【LeetCode 46】【LeetCode 47】全排列

【LeetCode 46】【LeetCode 47】全排列

46

    public static List> permute(int[] nums) {
    	List ret = new ArrayList();
    	List> list = new ArrayList>();
    	boolean[] read = new boolean[nums.length];
    	int deep = 0;
    	dfs(nums, ret, list, read, deep);
		return list;
    }
    
    private static void dfs(int[] nums, List ret, List> list, boolean[] read, int deep) {
    	if (deep == nums.length)
    	{
    		List copy = new ArrayList();
    		copy.addAll(ret);
    		list.add(copy);
    		return;
    	}
    	
    	for (int i = 0; i < nums.length; i++)
    	{
    		if (!read[i])
    		{
    			read[i] = true;
    			ret.add(nums[i]);
    			dfs(nums, ret, list, read, deep+1);
    			ret.remove(ret.size()-1);
    			read[i] = false;
    		}
    	}
    }
    

47

    public static List> permuteUnique(int[] nums) {
    	Arrays.sort(nums);
    	List ret = new ArrayList();
    	List> list = new ArrayList>();
    	boolean[] read = new boolean[nums.length];
    	int deep = 0;
    	dfs(nums, ret, list, read, deep);
		return list;
    }
    
    private static void dfs(int[] nums, List ret, List> list, boolean[] read, int deep) {
    	if (deep == nums.length)
    	{
    		List copy = new ArrayList();
    		copy.addAll(ret);
    		list.add(copy);
    		return;
    	}
    	
    	for (int i = 0; i < nums.length; i++)
    	{
    		if (i > 0 && nums[i] == nums[i-1] && read[i-1] == false) 
    			continue;
    		if (!read[i])
    		{
    			read[i] = true;
    			ret.add(nums[i]);
    			dfs(nums, ret, list, read, deep+1);
    			ret.remove(ret.size()-1);
    			read[i] = false;
    		}
    	}
    }