During the interview or written test, I encountered the following 4 hand-tearing algorithms about arrangement and combination many times. Take a note here and check the method in the future:
1. An array without duplicate elements, find the full arrangement;
2. Arrays with repeated elements, find the full arrangement;
3. For an array without duplicate elements, find the combination [subset];
4. An array with repeated elements, find the combination;
The above four types of questions can be implemented using a unified template, as shown below:
/* * [Combination &&Arrangement] *List all the combinations of numbers in an array, such as 1 and 2 as 1, 2, 12, 21. *This question can be expanded into four: *1. Arrays without duplicate numbers, find combinations*2. Arrays with duplicate numbers, find combinations*3. Arrays without duplicate numbers, find full arrangement*4. Arrays with duplicate numbers, find full arrangement*[General idea (recursion)]: *Define a function: select a combination prefix from the candidate set candicate *Each time remove a number from the candidate set candicate, and add prefix to print prefix; *Recursively remove the next number from the new candidate and add prefix *[Control for recursion] *Use hashset to save prefix. Before printing, determine whether the hashset contains the currently generated prefix. *If there is no, print it and add hashset; if there is, don't print it *[Combination--》 arrangement] *Simply add a judgment before printing: If the candidate set candicate is empty, it means that the traversal is completed once and an arrangement is generated, and you can print */package xh.offer.practice;import java.util.Arrays;import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.List;public class listAllGroup{ public static void main(String[] args) { String [] array = {"1","2"}; String [] repeat = {"1","2","1"}; listAllGroup test = new listAllGroup(); System.out.println("*********no repeat list*********"); test.listAllNoRepeate(Arrays.asList(array),"");//Initialize prefix = "" System.out.println("********* repeate list******"); HashSet<String> noRepeateSet = new HashSet<String>(); test.listAllRepeate(Arrays.asList(repeate), "", noRepeateSet); System.out.println("*************** no repeat premutation******************************"); test.premutationNoRepeate(Arrays.asList(array),""); System.out.println("***************************repeate premutation***************************"); HashSet<String> repeatSet = new HashSet<String>(); test.premutationRepeate(Arrays.asList(repeate),"", repeatSet); } //Combination without duplication public void listAllNoRepeate(List<String> candicate,String prefix){ if(prefix.length() != 0) System.out.println(prefix);//The result length is not 0, then print out the combination for(int i = 0;i < candicate.size();i++){ //Convert list to linklist to facilitate operation List<String> tempList = new LinkedList<String>(candicate); //templist reduces a number and temporarily saves the number removed in templist String tempString = (String) tempList.remove(i); //Recursive listAllNoRepeate(tempList,prefix + tempString); } } //There is a duplicate combination, add hashset public void listAllRepeate(List<String> candidate,String prefix,HashSet<String> res){ if(prefix.length() != 0 && !res.contains(prefix)){ System.out.println(prefix); res.add(prefix); } for(int i = 0;i < candidate.size();i++){ List<String> tempList = new LinkedList<String>(candicate); String tempString = tempList.remove(i); listAllRepeate(tempList, prefix+tempString, res);//Recursive} } //All arrangement without duplication, add 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 is a repeated full arrangement, add hashset to assist in judgment and 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 < candidate.size();i++){ List<String> tempList = new LinkedList<String>(candicate); String tempString = tempList.remove(i); premutationRepeate(tempList, prefix+tempString, res); } } } The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.