查找数组中长度为k的所有子集

  • Z时代
  • 2024-01-10
  • 分类：问答

给定一组{1,2,3,4,5...n}n个元素，我们需要找到长度为k的所有子集。

例如，如果n = 4且k = 2，output将是{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}。

我什至不知道如何开始。我们不必使用诸如next_permutation等的内置库函数。

需要使用C / C ++或Java的算法和实现。

回答：

递归是您完成此任务的朋友。

对于每个元素-如果“ guess”在当前子集中，则使用guess和较小的超集递归调用，您可以从中选择。对“是”和“否”的猜测都这样做-将导致所有可能的子集。

在stop子句中可以轻松地将自己约束到一定长度。

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的所有子集 的全部内容， 来源链接： utcz.com/qa/420370.html

回到顶部