Как вернуть все подмножества размера k набора, используя рекурсию?

Question

Я выполняю лабораторное задание, в котором мне нужно вернуть все подмножества определенного размера k, используя рекурсию.Функция принимает набор S и это значение k.Я делаю это на Java;Я уже видел ответы на этот вопрос, но они в C, и я изо всех сил пытаюсь установить связь между этими двумя языками.

Я уже написал функцию для определения набора мощности данного набора S с использованием рекурсии и понимания работы этого кода (показано ниже).Я больше всего борюсь с выяснением базовых и рекурсивных случаев для этой проблемы, поэтому я действительно не добился успеха в написании работающего кода.Для решения этой проблемы нам не разрешено создавать наборы мощности из функции, которую мы уже написали, а затем выбирать подмножества правильного размера;мы должны сделать это более эффективно.

public static Set<Set<String>> allSubsets(Set<String> s) {
    Set<Set<String>> pSet = new HashSet<>();
    Set<String> temp = new HashSet<>();
    temp.addAll(s);

    // base case
    // if temp is empty set, add the empty set to the powerset
    if (temp.isEmpty()) {
        pSet.add(temp);
    }

    // recursive case
    else {
        Iterator<String> itr = temp.iterator();
        String current = itr.next();
        temp.remove(current);
        Set<Set<String>> pSetTemp = allSubsets(temp);
        for (Set<String> x : pSetTemp) {
            pSet.add(x);
            Set<String> copySubset = new HashSet<>();
            copySubset.addAll(x);
            copySubset.add(current);
            pSet.add(copySubset);
        }
    }

    return pSet;

}

Как я уже сказал, этот код работает, я просто не могу решить вторую часть лабораторной работы, запрашивая функцию, которая находит подмножества определенного размера k.

Answer 1

Вот пример в JavaScript, который должен дать вам несколько советов.

function f(S, k){
  if (S.size == k)
    return [S]
  if (k == 0)
    return [new Set]

  let result = []

  for (let e of S){
    S.delete(e)
    let smaller = f(new Set(S), k - 1)
    for (let s of smaller){
      s.add(e)
      result.push(s)
    }
  }

  return result
}

var S = new Set([1, 2, 3, 4, 5])

console.log(JSON.stringify(
  f(S, 3).map(s => Array.from(s))))