关键词：
【中文标题】如何在Java中递归地从N元素集中生成所有k元素子集【英文标题】：How to Generate all k-elements subsets from an N-elements set recursively in Java 【发布时间】：2011-05-05 03:17:53 【问题描述】：所以我遇到了这个问题，试图从给定的 N 元素集中找到所有 k 元素子集。我知道使用公式 C(n,k)=C(n-1, k-1)+C(n-1, k) 的 k 子集的总数是多少，我也知道怎么做以迭代的方式，但是当我尝试考虑递归解决方案时，我陷入了困境。谁能给我一个提示？ 谢谢！
【问题讨论】：
你应该阅读格雷码。 你会如何迭代，迭代有什么问题？ @MB，因为这是作业要求的，我怀疑。 @MB，在迭代中没有奇迹发生。简单的话是蹩脚的。 @Woot4Moo：我提供了一些... 【参考方案1】：对于集合的每个元素，取那个元素，然后依次添加到剩余 N-1 个元素集合的所有 (k-1) 个子集。
“那是一个黑暗而暴风雨的夜晚，船长说……”
【讨论】：
我真的需要知道如何将其转换为递归方法，因为如前所述，我有一个涉及嵌套循环的迭代解决方案，但不知道如何将其转换为递归方法。 那是递归的方法！它说产生 N 集的 k 子集的问题与获取 N 的每个元素，然后计算剩余的 N-1 大小集的 k-1 集相同。当 K 达到 1 时，计算出 hte 子集是微不足道的。 对不起，你是对的！我想评论作为迭代解决方案的第二个答案，但它消失了，所以我最终在错误的地方发表评论。 这有重复。没有这些就好了。【参考方案2】：更好
这对于k=0 的情况是错误的，因为我认为它会返回一个包含空集的集合，这不太正确。反正。这里还有一个迭代，如果目标是纯递归的，你可以用递归替换它。这是对wikipedia: powerset 给出的算法的相当简单的修改。我将把修复角落案例 (k=0) 的工作留给读者。
这不是正确的尾递归，在大多数 JVM 中并不重要。 （我猜 IBM JVM 是这样做的……）
class RecursivePowerKSet
static public <E> Set<Set<E>> computeKPowerSet(final Set<E> source, final int k)
if (k==0 || source.size() < k)
Set<Set<E>> set = new HashSet<Set<E>>();
set.add(Collections.EMPTY_SET);
return set;
if (source.size() == k)
Set<Set<E>> set = new HashSet<Set<E>>();
set.add(source);
return set;
Set<Set<E>> toReturn = new HashSet<Set<E>>();
// distinguish an element
for(E element : source)
// compute source - element
Set<E> relativeComplement = new HashSet<E>(source);
relativeComplement.remove(element);
// add the powerset of the complement
Set<Set<E>> completementPowerSet = computeKPowerSet(relativeComplement,k-1);
toReturn.addAll(withElement(completementPowerSet,element));
return toReturn;
/** Given a set of sets S_i and element k, return the set of sets S_i U k */
static private <E> Set<Set<E>> withElement(final Set<Set<E>> source, E element)
Set<Set<E>> toReturn = new HashSet<Set<E>>();
for (Set<E> setElement : source)
Set<E> withElementSet = new HashSet<E>(setElement);
withElementSet.add(element);
toReturn.add(withElementSet);
return toReturn;
public static void main(String[] args)
Set<String> source = new HashSet<String>();
source.add("one");
source.add("two");
source.add("three");
source.add("four");
source.add("five");
Set<Set<String>> powerset = computeKPowerSet(source,3);
for (Set<String> set : powerset)
for (String item : set)
System.out.print(item+" ");
System.out.println();
仅限电源组 这可能不会完全到达那里，也不是很优雅，但它会递归计算完整的 powerset，然后（迭代地）修剪它的大小。
class RecursivePowerSet
static public <E> Set<Set<E>> computeConstrainedSets(final Set<Set<E>> source, final SizeConstraint<Set<E>> constraint)
Set<Set<E>> constrained = new HashSet<Set<E>>();
for (Set<E> candidate : source)
if (constraint.meetsConstraint(candidate))
constrained.add(candidate);
return constrained;
static public <E> Set<Set<E>> computePowerSet(final Set<E> source)
if (source.isEmpty())
Set<Set<E>> setOfEmptySet = new HashSet<Set<E>>();
setOfEmptySet.add(Collections.EMPTY_SET);
return setOfEmptySet;
Set<Set<E>> toReturn = new HashSet<Set<E>>();
// distinguish an element
E element = source.iterator().next();
// compute source - element
Set<E> relativeComplement = new HashSet<E>(source);
relativeComplement.remove(element);
// add the powerset of the complement
Set<Set<E>> completementPowerSet = computePowerSet(relativeComplement);
toReturn.addAll(completementPowerSet);
toReturn.addAll(withElement(completementPowerSet,element));
return toReturn;
static private <E> Set<Set<E>> withElement(final Set<Set<E>> source, E element)
Set<Set<E>> toReturn = new HashSet<Set<E>>();
for (Set<E> setElement : source)
Set<E> withElementSet = new HashSet<E>(setElement);
withElementSet.add(element);
toReturn.add(withElementSet);
return toReturn;
public static void main(String[] args)
Set<String> source = new HashSet<String>();
source.add("one");
source.add("two");
source.add("three");
source.add("four");
source.add("five");
SizeConstraint<Set<String>> constraint = new SizeConstraint<Set<String>>(3);
Set<Set<String>> powerset = computePowerSet(source);
Set<Set<String>> constrained = computeConstrainedSets(powerset, constraint);
for (Set<String> set : constrained)
for (String item : set)
System.out.print(item+" ");
System.out.println();
static class SizeConstraint<V extends Set>
final int size;
public SizeConstraint(final int size)
this.size = size;
public boolean meetsConstraint(V set)
return set.size() == size;
【讨论】：
@user497302：为什么不呢？它递归地计算所有 k 子集……编译它，它就可以工作了。【参考方案3】：这是一些伪代码。您可以通过在执行过程中存储每个调用的值以及在递归调用之前检查调用值是否已经存在来减少相同的递归调用。
以下算法将包含除空集之外的所有子集。
list * subsets(string s, list * v)
if(s.length() == 1)
list.add(s);
return v;
else
list * temp = subsets(s[1 to length-1], v);
int length = temp->size();
for(int i=0;i<length;i++)
temp.add(s[0]+temp[i]);
list.add(s[0]);
return temp;
【讨论】：
列表元素的所有排列(代码片段)
...选取一个元素作为排列的首元素，将剩余n-1的序列传入子递归函数k[start],k[i]=k[i],k[start]func1(k,start+1,end)k[start],k[i]=k[i],k[start]#将替换后的序列重置为原来的序列，确保后续循环中，选出的首元素是没选择过的元素 #递归层数从... 查看详情
如何在两个排序数组的并集中找到第 k 个最小的元素？
】如何在两个排序数组的并集中找到第k个最小的元素？【英文标题】：Howtofindthekthsmallestelementintheunionoftwosortedarrays?【发布时间】：2011-06-0405:22:07【问题描述】：这是一道作业题，已经介绍过二分查找：给定两个数组，分别按升... 查看详情
动态规划之最大递增子序列
...） 对于求一个数组N的最大递增子序列的问题，如何把这个问题转化成适合使用动态规划求解的形式呢？ 构造数组DP[ ],使得DP[i]为以N[i]结尾的最大递增子序列的长度，那么对于N[i]，DP[i]就等于MAXDP[K]+1 ,其... 查看详情
如何生成所有长度为 n 且设置了 k 位的二进制模式？ （使用递归）
】如何生成所有长度为n且设置了k位的二进制模式？（使用递归）【英文标题】：Howtogenerateallbinarypatternsoflengthnwithkbitsset?(usingrecursion)【发布时间】：2018-02-1206:18:26【问题描述】：我想编写一个函数来生成所有长度为n且设置了k位... 查看详情
所有长度为 k 的子数组的元素的乘积之和
】所有长度为k的子数组的元素的乘积之和【英文标题】：Sumofproductsofelementsofallsubarraysoflengthk【发布时间】：2016-01-0123:58:20【问题描述】：给出一个长度为n的数组。求子数组元素的乘积之和。说明数组A=[2,3,4]，长度为3。子数组... 查看详情
PostgreSQL 在递归查询中找到所有可能的组合（排列）
】PostgreSQL在递归查询中找到所有可能的组合（排列）【英文标题】：PostgreSQLfindallpossiblecombinations(permutations)inrecursivequery【发布时间】：2015-08-1112:25:57【问题描述】：输入是一个长度为“n”的数组。我需要生成数组元素的所有可... 查看详情
php实现全排列（递归算法）
...在排列Pi前面加上前缀i的排列，那么n个元素的全排列可递归定义为： ①如果n=1，则排列P只有一个元素i； ②如果n>1，则全排列P由排列(i)Pi构成；根据定义，可以看出如果已经生成（k-1）个元素的排列... 查看详情
如何从一组 k 元素中生成长度为 n 的所有排列？
】如何从一组k元素中生成长度为n的所有排列？【英文标题】：HowcanIgenerateallpermutationsoflengthnfromasetofkelements?【发布时间】：2020-08-1821:04:34【问题描述】：例如，我有一组k=5元素[1,2,3,4,5]，我想要长度为n=2的所有排列。1,21,31,41,52,1... 查看详情
选第k小元素：特定分治策略(代码片段)
...A1的元素数量大于等于K，即第K个元素在第一组内：在A1中递归查找第k小元素。若A1、A2元素个数之和大于等于K，即中项m为第K个元素。返回m。第K个元素在第三组：在A3中递归寻找第（k-|A1、A2元素数量之和|）小元素。3. 设计n&... 查看详情
分治与递归-线性时间选择(代码片段)
问题描述：给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k个元素。算法描述：算法实现：#include<stdio.h>#include<stdlib.h>intmain()voidsord(inta[],inth,intt);intselectorder(intx,inta[],inth,intt);intpartition(inta[],int 查看详情
java题目好难啊？求大侠解答，谢谢、、设计算法求解从集合1...n中选取k（k<=n)个元素的所有组合。
...t[5];//为数组赋初值for(inti=0;i<arr.length;i++)arr[i]=i+1;//开始递归从下表0开始依次取0,1,2...个元素存到list中//for(inti=0;i<=arr.length;i++)////List<Integer>l=newArrayList<Integer>();//start(arr,0,i,l);//List<Integer>l=newArrayList<Integer>();//s... 查看详情
清除后如何将元素推送到向量？
】清除后如何将元素推送到向量？【英文标题】：Howtopushelementstovectorafteritiscleared?【发布时间】：2019-07-1812:58:45【问题描述】：我得到了一个n元素数组和一个整数K。我必须以相反的顺序打印K元素的子数组。我将元素存储在向量... 查看详情
hiho#1502：最大子矩阵（元素和不超过k）
...个NxM的矩阵A和一个整数K，小Hi希望你能求出其中最大（元素数目最多）的子矩阵，并且该子矩阵中所有元素的和不超过K。输入第一行包含三个整数N、M和K。以下N行每行包含M个整数，表示A。对于40%的数据，1<=N,M<=10 对于... 查看详情
在n个元素的数组中获取k个元素的所有组合问题
可以写循环，也可以用模块。百度许久找到一个博客http://blog.sina.com.cn/s/blog_4a0824490101f1kc.html详细介绍了Algorithm::Combinatorics受此启发，又找到了Math::Combinatorics由于前面的博客介绍了Algorithm::Combinatorics，所以本博客介绍一下Math::Comb... 查看详情
选第k小元素：分治策略(代码片段)
...每一组的中位数，任意排序方法，比如插入排序。3. 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。4. 用x来分割数组，设小于等于x的个数为k，大于x的... 查看详情
如何通过在 oracle 中提供子元素 ID 来获取所有父元素？
】如何通过在oracle中提供子元素ID来获取所有父元素？【英文标题】：HowcanIgetalltheparentelementbyprovidingchildelementIDinoracle?【发布时间】：2018-07-2006:16:32【问题描述】：我的Oracle表是这样的ID|ParentID-----------------1|02|13|24|35|3如果我只知... 查看详情
如何在指数级大列表中找到第 k 个最大的元素？
】如何在指数级大列表中找到第k个最大的元素？【英文标题】：HowcanIfindthek-thlargestelementinanexponentiallylargelist?【发布时间】：2021-11-0104:17:26【问题描述】：假设有n组实数：S[1],S[2],...,S[n]。关于这些集合，我们知道两件事：每个... 查看详情
一维数组求最大子数组的和（首位相邻32位）
...个整数数组中最大子数组的和，细化分析：1，在所有以元素tail结尾的子数组中，选出元素和最大的子数组，tail=1,2...n。2，以元素k结尾的和最大的子数组是包含以元素tail-1结尾的和最大的子数组还是就只有元素tail这一个元素，... 查看详情