java数组排列组合问题汇总
面试或笔试中，多次遇到以下4个关于排列组合的手撕算法，这里做个笔记，方法日后查阅：
1.无重复元素的数组，求全排列；
2.有重复元素的数组，求全排列；
3.无重复元素的数组，求组合【子集】；
4.有重复元素的数组，求组合；
以上四类题，可以用统一的模板实现，如下所示：
/*
*【组合&&排列】
*把一个数组里的数组合全部列出，比如1和2列出来为1,2,12,21.
*这个题目可以扩展成四个：
*1.无重复数字的数组，求组合
*2.有重复数字的数组，求组合
*3.无重复数字的数组，求全排列
*4.有重复数字的数组，求全排列
*【通用思路（递归）】：
*定义一个函数：从候选集candicate中选取一个组合prefix
*每次从候选集candicate中remove一个数，并加入前缀prefix，打印prefix；
*再递归从新的candicate中remove下一个数，并加入prefix
*【对于重复的控制】
*采用hashset保存prefix，打印之前，判断hashset中是否包含当前生成的prefix，
*没有则打印，并加入hashset；有则不打印
*【组合--》排列】
*只需在打印前加一个判断：若候选集candicate为空，表示遍历完一次，生成一个排列，可打印
*/
packagexh.offer.practice;
importjava.util.Arrays;
importjava.util.HashSet;
importjava.util.LinkedList;
importjava.util.List;
publicclasslistAllGroup{
publicstaticvoidmain(String[]args){
String[]array={"1","2"};
String[]repeate={"1","2","1"};
listAllGrouptest=newlistAllGroup();
System.out.println("**********norepeatelist*******");
test.listAllNoRepeate(Arrays.asList(array),"");//初始化prefix=""
System.out.println("**********repeatelist*******");
HashSetnoRepeateSet=newHashSet();
test.listAllRepeate(Arrays.asList(repeate),"",noRepeateSet);
System.out.println("**************norepeatepremutation********************");
test.premutationNoRepeate(Arrays.asList(array),"");
System.out.println("*********************repeatepremutation**********************");
HashSetrepeateSet=newHashSet();
test.premutationRepeate(Arrays.asList(repeate),"",repeateSet);
}
//无重复的组合
publicvoidlistAllNoRepeate(Listcandicate,Stringprefix){
if(prefix.length()!=0)
System.out.println(prefix);//结果长度不为0,则打印输出该组合
for(inti=0;itempList=newLinkedList(candicate);
//templist减少一个数字，并暂存templist中去除的数字
StringtempString=(String)tempList.remove(i);
//递归
listAllNoRepeate(tempList,prefix+tempString);
}
}
//有重复的组合,加入hashset
publicvoidlistAllRepeate(Listcandicate,Stringprefix,HashSetres){
if(prefix.length()!=0&&!res.contains(prefix)){
System.out.println(prefix);
res.add(prefix);
}
for(inti=0;itempList=newLinkedList(candicate);
StringtempString=tempList.remove(i);
listAllRepeate(tempList,prefix+tempString,res);//递归
}
}
//无重复的全排列，加入判断candicate.size()==0
publicvoidpremutationNoRepeate(Listcandicate,Stringprefix){
if(candicate.size()==0){
System.out.println(prefix);
}
for(inti=0;itempList=newLinkedList(candicate);
StringtempString=tempList.remove(i);
premutationNoRepeate(tempList,prefix+tempString);
}
}
//有重复的全排列，加入hashset辅助判断输出
publicvoidpremutationRepeate(Listcandicate,Stringprefix,HashSetres){
if(candicate.size()==0&&!res.contains(prefix)){
System.out.println(prefix);
res.add(prefix);
}
for(inti=0;itempList=newLinkedList(candicate);
StringtempString=tempList.remove(i);
premutationRepeate(tempList,prefix+tempString,res);
}
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。