package String_process;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月13日 16:36
 * @description: 给定一个可包含重复数字的序列nums,按任意顺序 返回所有不重复的全排列。
 */
public class Permutation2 {
 public static void main(String[] args) {
 Scanner sr = new Scanner(System.in);
 String []arr = sr.nextLine().split(" ");
 int [] nums = new int[arr.length];
 for(int i = 0; i<arr.length;i++){
 nums[i] = Integer.parseInt(arr[i]);
 }
 Arrays.sort(nums);
 System.out.println(new Permutation2_solution().permuteUnique(nums));
 }
}

class Permutation2_solution{
 List<List<Integer>> res = new ArrayList<>();
 boolean vis[];
 public List<List<Integer>> permuteUnique(int [] nums){
 List<Integer> trace = new ArrayList<>();
 vis = new boolean[nums.length];
 int ids = 0;
 dfs(nums,vis,trace,ids);
 return res;
 }
 public void dfs(int []nums,boolean []vis,List<Integer> trace,int ids){
 if(trace.size() == nums.length){
 res.add(new ArrayList<>(trace));
 return;
 }
 //for循环保证了从数组中从前往后一个一个取值,再用if判断条件,所以nums[i-1]一定比nums[i]先被取值和判断
 //每递归一层都是在寻找数组对应递归深度位置的值,每一层用for循环来寻找
 for(int i = 0;i < nums.length; i++){
 //如果nums[i-1]被取值了,那vis[i-1]会被置1,只有递归再回退到这一层时再将它置0
 //当vis[i-1]==1时,说明nums[i-1]和nums[i]分别属于两层递归中,也就是我们要用这两个数分别放在数组的两个位置,这时不需要去重
 //但是当vis[i-1] == 0时,说明nums[i-1]和nums[i]属于同一层递归中(只是for循环进入了下一层循环),也就是要用这两个数放在数组中的同一个位置上,要去重
 //所以用vis[i-1] 可以判断是否是当前层次,当==0时,说明是同层,否则是不同层
 if(vis[i] || ( i>0 && nums[i] == nums[i-1] && !vis[i-1])){
 continue;
 }
 //做选择
 trace.add(nums[i]);
 vis[i] = true;
 //下一层 回溯
 dfs(nums,vis,trace,ids+1); //ids表示深度,for循环的i代表某深度下的层次
 //取消选择
 vis[i] = false;
 trace.remove(ids);
 }
 }
}