算法 集合的所有子集 全排列

Question

{1,2,3}的所有排列组合方式
{{1},{2},{3}}
{{1},{2,3}}
{{1,2},{3}}
{{1,3},{2}}
{{123}}
请大家给个想法或者算法实现

Answer 1

publicListallSubsetPermutation(int[]nums){if(nums==null||nums.length==0)returnnull;Queueq=newLinkedList();q.add(newLinkedList());for(intn:nums){intsize=q.size();while(size-->0){Listlist=q.poll();for(inti=0;i

Answer 2

这个我想到高中的排列组合，用的是隔板法(不太记得是不是叫这个)。比如，隔板是说在1|2|3|4数字中间放的分隔板。分成一个集合，不用隔板分成两个集合，放一个隔板，共C(n-1,1),比如{1|234}{12|34}{123|4}分成k个集合，放k-1个隔板，共C(n-1,k-1)种。然后想如何实现隔板，给隔板编号1,2,...,n-1于是每次放k个隔板意味着从n-1个数中取出k个数字，就是组合数，可以用回溯遍历出来seq[]放k的数字seq[]=-1表示这个位置没有数字DFS(index){if(index==k){print();return;}for(inti=1;i