(알고리즘) 부분집합 합 구하기

집합이 존재 할때 특정 갯수, 그리고 합이 일정한 부분집합이 존재하는지 구하기

public class SubsetMake {

private static int[] number;
    private static int M;
    private static int N;
   
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
//총 갯수
N=Integer.parseInt(reader.readLine());
String[] line=reader.readLine().split(" ");
ArrayList<Integer> ar=new ArrayList<Integer>();
number=new int[line.length];
for(int i=0;i<number.length;i++)
{
number[i]=Integer.parseInt(line[i]);
ar.add(number[i]);

}
//부분집합의 갯수
M=Integer.parseInt(reader.readLine());


if(subset_make(ar))
           System.out.println("True");
        if(!subset_make(ar))
        System.out.println("False");


}
private static boolean subset_make(ArrayList<Integer> ar){

if(ar.size()==M){
int flag=ar.get(0);
for(int i=1;i<ar.size();i++)
if(ar.get(0)!=ar.get(i))return false;

return true;
}
boolean ret=false;
for(int i=0;i<ar.size();i++){
for(int j=i+1;j<ar.size();j++){
ArrayList<Integer> next=new ArrayList<Integer>();
int pack=ar.get(i)+ar.get(j);
next.add(pack);
for(int k=0;k<ar.size();k++){
if(i!=k&&j!=k)next.add(ar.get(k));
}
ret=subset_make(next);
if(ret==true)
return true;
}
}

return ret;
}

}