查找数组中长度为 k 的所有子集 [英] Find all subsets of length k in an array
问题描述
给定一组 {1,2,3,4,5...n}
的 n 个元素,我们需要找到长度为 k 的所有子集.
Given a set {1,2,3,4,5...n}
of n elements, we need to find all subsets of length k .
例如,如果 n = 4 且 k = 2,output
将是 {1, 2}, {1, 3}, {1, 4}, {2,3}, {2, 4}, {3, 4}
.
For example, if n = 4 and k = 2, the output
would be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
.
我什至不知道如何开始.我们不必使用 next_permutation 等内置库函数.
I am not even able to figure out how to start. We don't have to use the inbuilt library functions like next_permutation etc.
需要 C/C++ 或 Java 中的算法和实现.
Need the algorithm and implementation in either C/C++ or Java.
推荐答案
递归是您完成此任务的朋友.
Recursion is your friend for this task.
对于每个元素 - 猜测"它是否在当前子集中,并递归调用猜测和您可以从中选择的较小超集.对是"和否"猜测都这样做 - 将产生所有可能的子集.
在停止子句中可以轻松地将自己限制在一定的长度.
For each element - "guess" if it is in the current subset, and recursively invoke with the guess and a smaller superset you can select from. Doing so for both the "yes" and "no" guesses - will result in all possible subsets.
Restraining yourself to a certain length can be easily done in a stop clause.
Java 代码:
private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
//successful stop clause
if (current.size() == k) {
solution.add(new HashSet<>(current));
return;
}
//unseccessful stop clause
if (idx == superSet.size()) return;
Integer x = superSet.get(idx);
current.add(x);
//"guess" x is in the subset
getSubsets(superSet, k, idx+1, current, solution);
current.remove(x);
//"guess" x is not in the subset
getSubsets(superSet, k, idx+1, current, solution);
}
public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
List<Set<Integer>> res = new ArrayList<>();
getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
return res;
}
调用方式:
List<Integer> superSet = new ArrayList<>();
superSet.add(1);
superSet.add(2);
superSet.add(3);
superSet.add(4);
System.out.println(getSubsets(superSet,2));
将产生:
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
这篇关于查找数组中长度为 k 的所有子集的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!