Algorithm] 부분집합(powerset) (JAVA)

1. 부분집합(powerset)

배열의 모든 부분집합을 구하는 방법이다.
예를 들어, {1,3,5}의 부분집합은
{1,3,5}
{1,3}
{1,5}
{1}
{3,5}
{3}
{5}
가 될 것이다.

코드의 핵심은 17~20번줄이다.
sel이란 selected를 의미하는 준말로 작성하였다.
말 그대로, 선택여부를 판단하기 위한 배열이다.

powerset 재귀함수로 들어가기전에 true를 해준다.
그리고 해당 재귀가 기저조건에 의해 종료가 되면, 원래대로 돌려주기 위해서
false로 바꿔준다.

재귀의 순서를 천천히 따라가다보면 이해할 수 있을 것이다.
애증의 재귀..

public class 부분집합 {
    public static void main(String[] args) {
        int[] arr = {1,3,5};
        powerset(arr, 0, new boolean[arr.length]);
    }
    
    static void powerset(int[]arr, int idx, boolean[] sel) {
        if(idx == arr.length) {
            
            for(int i=0; i<sel.length; i++) {
                if(sel[i])
                    System.out.print(arr[i]+" ");
            }System.out.println();
            return;
        }
        
        sel[idx]=true;
        powerset(arr, idx+1, sel);
        sel[idx]=false;
        powerset(arr, idx+1, sel);
    }
    
}