给定一组{1,2,3,4,5...n}n个元素,我们需要找到长度为k的所有子集。
{1,2,3,4,5...n}
例如,如果n = 4且k = 2,output将是{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}。
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]]