package leetcode_50;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.List;

/***

 *

 * @author pengfei_zheng

 * 给定数组元素可能重复，求出所有全排列

 */

public class Solution47 {

    public static List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        if(nums==null || nums.length==0) return ans;

        boolean[] used = new boolean[nums.length];

        List<Integer> list = new ArrayList<Integer>();

        Arrays.sort(nums);

        prem(ans,list,nums,used);

        return ans;

    }

    private static void prem(List<List<Integer>> list, List<Integer> tempList, int[] nums, boolean[] used) {

        if(tempList.size()==nums.length){

            list.add(new ArrayList<>(tempList));

        }

        else{

            for(int i = 0; i < nums.length; i++){

                if(used[i] || i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;

                used[i]=true;

                tempList.add(nums[i]);

                prem(list,tempList,nums,used);

                used[i]=false;

                tempList.remove(tempList.size()-1);

            }

        }

    }

    public static void main(String[]args){

        int []nums={3,0,3,3};

        List<List<Integer>> list = permute(nums);

        for(List<Integer> item:list){

            System.out.println(item);

        }

    }

}