查找长度为k的所有子集在一个数组

本文介绍了查找长度为k的所有子集在一个数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定一组 {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，输出是 {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的code：

Java code:

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]]