java array permutation and combination problem summary

In the interview or written test, I have encountered the following 4 hand-tear algorithms about permutation and combination many times. Here is a note for reference of the method in the future:

1. Array without repeating elements, complete arrangement;
2. Array with repeated elements, complete arrangement;
3. Array without repeated elements, to find the combination [subset];
4. There are repeated elements of the array, find the combination;

The above 4 types of problems can be realized with the template of unified 1, as shown below:

/*
 * The combination of && Arrange 】 
 * the 1 All combinations of numbers in the array are listed, for example 1 and 2 A list of 1,2,12,21.
 * This problem can be expanded to 4 A: 
 *1. No duplicate number array, seek combination 
 *2. Have the array of duplicate numbers, find the combination 
 *3. No duplicate number array, complete arrangement 
 *4. An array of duplicate digits, complete in order 
 * [General idea (recursion)] : 
 * define 1 A function: from the candidate set candicate Select the 1 A combination of prefix
 * Each time from the candidate set candicate In the remove1 Number, and add the prefix prefix To print prefix ; 
 * Recursion from the new candicate In the remove Under the 1 Number, and add prefix
 * [Control for repetition] 
 * using hashset save prefix , before printing, judge hashset Contains the currently generated prefix . 
 * No then print and add hashset ; Some do not print 
 * The combination of -- "Arrange 】 
 * Just add it before printing 1 Judgment: if candidate set candicate Is empty, indicating that the traversal is complete 1 Time, generate 1 A permutation, printable 
 */

package xh.offer.practice;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class listAllGroup{
  public static void main(String[] args) {
    String [] array = {"1","2"};
    String [] repeate = {"1","2","1"};
    listAllGroup test = new listAllGroup();
    System.out.println("**********no repeate list*******");
    test.listAllNoRepeate(Arrays.asList(array),"");// Initialize the prefix = ""
    System.out.println("**********repeate list*******");
    HashSet<String> noRepeateSet = new HashSet<String>();
    test.listAllRepeate(Arrays.asList(repeate), "", noRepeateSet);
    System.out.println("**************no repeate premutation********************");
    test.premutationNoRepeate(Arrays.asList(array),"");
    System.out.println("*********************repeate premutation**********************");
    HashSet<String> repeateSet = new HashSet<String>();
    test.premutationRepeate(Arrays.asList(repeate),"", repeateSet);
  }
  // No duplicate combinations 
  public void listAllNoRepeate(List<String> candicate,String prefix){ 
    if(prefix.length() != 0)
      System.out.println(prefix);// The result length is not zero 0, The combination is printed out 

    for(int i = 0;i < candicate.size();i++){
      // will list Converted to linklist Linked list, easy to operate 
      List<String> tempList = new LinkedList<String>(candicate);
      //templist To reduce 1 Numbers, and temporary storage templist The number removed from 
      String tempString = (String) tempList.remove(i);
      // recursive 
      listAllNoRepeate(tempList,prefix + tempString);
    }
  }

  // There are repeated combinations , join hashset
  public void listAllRepeate(List<String> candicate,String prefix,HashSet<String> res){
    if(prefix.length() != 0 && !res.contains(prefix)){
      System.out.println(prefix);
      res.add(prefix);
    }

    for(int i = 0;i < candicate.size();i++){
      List<String> tempList = new LinkedList<String>(candicate);
      String tempString = tempList.remove(i);
      listAllRepeate(tempList, prefix+tempString, res);// recursive 
    }
  }

  // No repetition of the full permutation, adding judgment candicate.size() == 0
  public void premutationNoRepeate(List<String> candicate,String prefix){
    if(candicate.size() == 0){
      System.out.println(prefix);
    }

    for(int i = 0;i < candicate.size();i++){
      List<String> tempList = new LinkedList<String>(candicate);
      String tempString = tempList.remove(i);
      premutationNoRepeate(tempList,prefix+tempString);
    }
  }

  // There are repeated full permutations, added hashset Auxiliary judgment output 
  public void premutationRepeate(List<String> candicate,String prefix,HashSet<String> res) {
    if(candicate.size() == 0 && !res.contains(prefix)){
      System.out.println(prefix);
      res.add(prefix);
    }

    for(int i = 0;i < candicate.size();i++){
      List<String> tempList = new LinkedList<String>(candicate);
      String tempString = tempList.remove(i);
      premutationRepeate(tempList, prefix+tempString, res);
    }  
  }

  }