java-求指定数组中指定个数的排列组合

古城微笑少年丶 2023-05-21 08:49 12阅读 0赞

真的是讨厌面试的那些数字排列组合题，时间久了总是容易忘记算法，

这里写个自己及朋友遇到的可能使用到的情况汇总

耐心的同学看注释应该能理解，可能写的繁琐（为了一个方法整全），但是应该够用

/**
     * @author huangw
     */
    public class Combination {
    	
    	/**
    	 * 递归实现排列组合
    	 * @param candidate  数组--数字集合
    	 * @param prefix  递归打印使用
    	 * @param size   当前数组选取位数，例如4个数字里面求3位组合传3即可  传0为当前数组的所有组合输出
    	 * @param resList 返回内容的数字字符串组合
    	 */
    	public static void recursive(List<Integer> candidate, String prefix, Integer size, List<String> resList){
    		if(size == 0) {
    			if(prefix.length() != 0) {
    				System.out.println(prefix);
    				resList.add(prefix);
    			}
    			
    		} else if(prefix.length() == size){
    			System.out.println(prefix);
    			resList.add(prefix);
    			return;
    		}
    		
    		for(int i=0; i<candidate.size(); i++){
    			List<Integer> temp = new LinkedList<Integer>(candidate);
    			int item = (int)temp.remove(i);  // 取出被删除的元素，这个元素当作一个组合用掉了
    			
    			//去重保留一种  例如12和21为同一种  123 132 321位同一种
    			for(int k = i; k > 0; k--) {//注释即为全排列
    				temp.remove(k-1);
    			}
    			
    			recursive(temp, prefix+item, size, resList);
    		}
    	}
    	
    	public static void main(String[] args) {
    		Integer[] array = {1,2,4};
    		List<Integer> list = Arrays.asList(array);
    		Set<Integer> set = new HashSet(list);//数字数组本身去重---利用set集合
    		List<Integer> newList = new ArrayList(set);
    		System.out.println(newList);
    		List<String> resList = new ArrayList<String>();
    		recursive(list, "", 3,resList);
    		System.out.println(resList);
    	}
    }

欢迎留言指导