부분집합

부분집합

집합에서 원소를 선택하는 것이다.

idx는 뽑으려고 하는 수의 인덱스다. 인덱스가 총 뽑을 수 있는 수의 개수(N)와 동일하면 끝난다. 

isSelected는 뽑은 수를 저장하는 배열이다. 이 코드에서는 값 없이 뽑은 수의 인덱스만 저장했다.

공집합, 모든 원소를 포함하는 집합도 포함한다.

private static void subSet(int idx){
   if(idx==N){
      for(int i=0;i<N;i++){
         System.out.println((isSelected[i]?input[i]:"X")+" ");
      }
      System.out.println();
      return;
   }
   
   isSelected[idx] = true;
   subSet(idx+1);
   
   isSelected[idx] = false;
   subSet(idx+1);
}

 

관련 문제

1182번: 부분수열의 합