Нахождение подмножеств размера к для заданного набора размера п

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 < Integer> к ArrayList <?> в строке 21 затмение говорит

Невозможно создать тип ArrayList <?> Как исправить это?

Answer 1

Вы можете использовать ArrayList<Object> повсюду. Это будет принимать любой объект. Если вам нужен определенный тип, который определяется вызывающим кодом, вам необходимо ввести параметр типового типа.

Обратите внимание, что в методе generatePerm, вы не должны использовать тест

if (input == "") 

Вместо этого, вы должны использовать:

if ("".equals(input)) 

Ваш текущий код будет успешным только если input является интернированы строка "". Он не будет работать, например, если input вычисляется как substring() с нулевой длиной. В общем, вы всегда должны сравнивать строки с .equals(), а не с == (за исключением особых условий, когда вы ищете идентификацию объекта, а не равномерность объекта).