生成长度不超过k的子集

Question

我已经编写了代码，能够从长度大于'k'的输入中生成长度为'k'的子集。

但我无法编写出生成所有长度不超过'k'的子集的代码。

public static void pset(List<Integer> original, List<Integer> lst, int k, int idx) {
    if(lst.size() == k) {
        System.out.println(lst);
        return;
    }

    if(idx == original.size()) {
        return;
    }

    lst.add(original.get(idx));
    pset(original,lst,k,idx+1);
    lst.remove(lst.size()-1);
    pset(original,lst,k,idx+1);
}

public static void main(String[] args) {
    var original = List.of(1,2,3,4);
    pset(original, new ArrayList<>(),2,0);
}

- curiousengineer

Answer 1

public static void pset(List<Integer> original, List<Integer> lst, int k, int idx) {
        if(idx ==  original.size() || lst.size() == k) {
            if (lst.size() <= k)
                System.out.println(lst);
            return;
        }


        lst.add(original.get(idx));
        pset(original,lst,k,idx+1);
        lst.remove(lst.size()-1);
        pset(original,lst,k,idx+1);
}

当 idx == original.size() 时，这意味着您通过获取它们的子集到达了列表的末尾，请检查所取子集的长度是否最多为 k。

- Mohamed Magdy

---

我建议将初始语句从if(idx == original.size())更改为if(idx == original.size() || lst.size() == k)，以便它不会不必要地递归。 - selbie

@MohamedMagdy，您能分享之前的建议吗？ - curiousengineer