//思路：
//Perms(nums[0...n-1]) = {取出一个数字} + Perms{nums[{0...n-1}-该数字]}

private List<List<Integer>> res;

private boolean[] visited; //标记元素是否已经被访问

public List<List<Integer>> permute(int[] nums) {
  res = new ArrayList<>();
  if(nums==null || nums.length==0){
    return res;
  }
  visited = new boolean[nums.length];
  List<Integer> p = new ArrayList<>();
  generatePermutation(nums,0,p);
  return res;
}

//产生排列
//p中保存一个存在index个元素的排列
//向这个排列的末尾添加第(index+1)个元素，获得包含(index+1)个元素的排列
private void generatePermutation(int[] nums,int index,List<Integer> p){
  if(index == nums.length){
    res.add(new ArrayList<>(p));
    return;
  }

  for(int i=0;i<nums.length;i++){
    if(!visited[i]){
      p.add(nums[i]);
      visited[i]=true;

      generatePermutation(nums,index+1,p);

      p.remove(p.size()-1);
      visited[i]=false;
    }
  }
  return;
}

@Test
public void test(){
  int[] nums = {1,2,3};
  List<List<Integer>> res=permute(nums);
  for(List<Integer> list : res){
    System.out.println(list);
  }
}

//思路：
//1、先对数组进行排序，这样如果存在重复元素，则这些元素是相邻的
//2、对于重复元素,最后一个元素加入排列
private List<List<Integer>> res;

private boolean[] visited;

public List<List<Integer>> permuteUnique(int[] nums) {
  res = new ArrayList<>();
  if(nums==null || nums.length==0){
    return res;
  }
  Arrays.sort(nums);

  visited = new boolean[nums.length];

  List<Integer> p = new ArrayList<>();
  generatePermutation(nums,0,p);

  return res;
}

private void generatePermutation(int[] nums,int index,List<Integer> p){
  if(index==nums.length){
    res.add(new ArrayList<>(p));
    return;
  }
  for(int i=0;i<nums.length;i++){
    if(!visited[i]){
      if(i>0 && (nums[i-1]==nums[i] && !visited[i-1])){
        // 为甚要加上这个 !visited[i-1]
        //实际上是指 nums[i-1] 和 nums[i] 相邻元素，并且都没有被访问，则后面的元素加入排列
        continue;
      }
      p.add(nums[i]);
      visited[i]=true;
      generatePermutation(nums,index+1,p);
      visited[i]=false;
      p.remove(p.size()-1);
    }
  }
  return;
}

@Test
public void test(){
  int[] nums = {1,1,2};
  List<List<Integer>> res=permuteUnique(nums);
  for(List<Integer> list : res){
    System.out.println(list);
  }
}

private List<String> res;

public List<String> letterCasePermutation(String S) {
  res = new ArrayList<>();
  if(S.length()==0){
    res.add(S);
    return res;
  }

  StringBuilder builder = new StringBuilder(S);
  replaceCh(0,builder);
  return res;
}

//替换 index 位置元素
private void replaceCh(int index, StringBuilder builder){
  if(index==builder.length()){
    res.add(builder.toString());
    return;
  }

  char ch = builder.charAt(index);
  if(Character.isLetter(ch)){
    builder.setCharAt(index,Character.toLowerCase(ch));
    replaceCh(index+1,builder);
    builder.setCharAt(index,Character.toUpperCase(ch));
    replaceCh(index+1,builder);
  }else{
    replaceCh(index+1,builder);
  }
  return;
}

@Test
public void test(){
  //String S = "a1b2";
  String S = "3z4";
  System.out.println(letterCasePermutation(S));
}

private List<List<Integer>> res;

public List<List<Integer>> combine(int n, int k) {
  res = new ArrayList<>();
  if(n<=0 || k<=0 || n<k){
    return res;
  }
  List<Integer> c= new ArrayList<>();
  findCombination(n,k,0,c);

  return res;
}

//c存储已经找到的组合
//从start开始搜索新的元素
private void findCombination(int n,int k,int start,List<Integer> c){
  if(k==c.size()){ //已经找到 k 个元素
    res.add(new ArrayList<>(c));
    return;
  }
  for(int i=start;i<=n;i++){
    c.add(i);
    findCombination(n,k,i+1,c);
    c.remove(c.size()-1);
  }
  return;
}

@Test
public void test(){
  int n=4;
  int k=2;
  List<List<Integer>> res=combine(n,k);
  for(List<Integer> list : res){
    System.out.println(list);
  }
}