java为给定的大小为n的集合查找大小为k的子集

Question

我正试图找出解决上述问题的办法，我想出了这个办法

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;


public class Subset_K {
public static void main(String[]args)
{
Set<String> x;
int n=4;
int k=2;
int arr[]={1,2,3,4};
StringBuilder sb=new StringBuilder();
for(int i=1;i<=(n-k);i++)
    sb.append("0");
for(int i=1;i<=k;i++)
    sb.append("1");
String bin=sb.toString();
x=generatePerm(bin);
Set<ArrayList <Integer>> outer=new HashSet<ArrayList <Integer>>();
for(String s:x){
    int dec=Integer.parseInt(s,2);
    ArrayList<Integer> inner=new ArrayList<Integer>();
    for(int j=0;j<n;j++){
        if((dec&(1<<j))>0)
            inner.add(arr[j]);
    }
    outer.add(inner);
}
for(ArrayList<Integer> z:outer){
    System.out.println(z);
}
}

public static Set<String> generatePerm(String input)
{
Set<String> set = new HashSet<String>();
if (input == "")
    return set;

Character a = input.charAt(0);

if (input.length() > 1)
{
    input = input.substring(1);

    Set<String> permSet = generatePerm(input);

    for (String x : permSet)
    {
        for (int i = 0; i <= x.length(); i++)
        {
            set.add(x.substring(0, i) + a + x.substring(i));
        }
    }
}
else
{
    set.add(a + "");
}
return set;
}
}

我正在处理一个用于测试的4元素集，并使用k=2。我试图做的是首先生成一个二进制字符串，其中设置了k位，而没有设置n-k位。现在使用这个字符串，我找到了这个字符串的所有可能的排列。然后使用这些排列，我输出集合中相应的元素。现在我无法理解这段代码的复杂性，因为我使用了其他人提供的generatePerm方法。有人能帮助我了解generatePerm方法的时间复杂度以及解决方案的总体时间复杂度吗。我在这里发现了这个问题的其他递归实现Find all subsets of length k in an array，但是我也不能理解它的复杂性。所以我需要一些帮助

此外，我还试图重新计算代码的因子，以便它不仅适用于整数，而且适用于所有类型的数据。我在泛型方面没有太多经验。因此，当我尝试修改ArrayList时<；整数>；到ArrayList<&燃气轮机；第21行eclipse说

Cannot instantiate the type ArrayList< ?> How do I correct that?

Answer 1

您可以在整个过程中使用ArrayList<Object>。它可以接受任何类型的对象。如果需要由调用代码确定的特定类型，则需要引入泛型类型参数

注意，在generatePerm方法中，不应使用测试

if (input == "")

相反，您应该使用：

if ("".equals(input))

只有当input是插入的字符串""时，当前代码才会成功。例如，如果将input计算为长度为零的substring()，则它将不起作用。一般来说，您应该始终将字符串与.equals()而不是与==进行比较（除非在非常特定的条件下，当您查找对象标识而不是对象相等时）