자바 알고리즘 부분집합 구하는 방법 CheetSheet

1. 재귀함수

public static void dfs(int idx,int sum) {
    if(idx >= N){
        if(sum == S) result++;
        return;
    }

    dfs(idx + 1,  sum + arr[idx]);
    dfs(idx + 1,  sum);
}

고르고 안고른 1/2 의 모든 부분집합을 따져본 방법이다. [1,2,3,4]가 있을 경우, 

 

   1         2          3         4

(O,X)  (O,X)   (O,X)   (O,X)   의 경우를 생각해서 고른 경우와 안고른 경우를 생각해보면 된다.

 

public static void dfs(int[] array, int idx, int choiceCnt, String result, int K){
	if(choiceCnt == 6){
    		System.out.println(result);
            return;
        }


    if(idx >= K) return;
    dfs(array, idx + 1, choiceCnt+1, result+array[idx]+" ",K);
    dfs(array, idx + 1, choiceCnt, result,K);
    }

 

특정 개수에 대한 제한을 걸면 위와 같아지는데, 고르고 안고른 모든 경우를 따지게 될 때, 특정 개수조건이 충족되면 작업을 수행하고 return 하면 된다. choiceCnt로 몇 개까지 O로 담아놨는지를 체크하는 로직만 추가된다.

 

또한 idx가 끝까지 도달했는데 6개를 담지 못했다면 나가리 처리한다.

 

 

 

2. 비트

 

for (int bit = 1; bit < (1 << N); bit++) {
    int sum = 0;
    for (int k = 0; k < N; k++) {
        if((bit & (1 << k)) != 0) {
            sum += arr[k];
        }
    }
    if( sum == S) {
        result++;
    }
}

 bit가 1부터 시작하는 이유는 빈 수열을 나타내는 경우가 `bit=0`일 때입니다. 빈 수열의 합은 0이므로, 이를 제외하기 위해 `bit`를 1부터 시작하게 됩니다. 그래서 1부터 `1 << N`까지 반복문을 돌리는 것이죠.

 

 더 깊게 들어가보면, `N`개의 원소가 있는 배열에서 만들 수 있는 모든 부분수열은 `2^N`개입니다. 그 중 빈 부분수열 1개를 제외한 나머지 `2^N - 1`개의 부분수열을 확인하는 것입니다. 그래서 `bit`를 1부터 시작해서 `1 << N`까지 반복문을 돌립니다. 이렇게 하면 빈 부분수열을 자연스럽게 제외할 수 있습니다.

 

 쉽게 설명하자면, 4개의 배열이 있을 때, 선택과 선택하지 않음을 bit (1,0)으로 구분하고, 그 경우의 수를 구하면 2^N이 됩니다. (OOOO 다 고름, OXOX 2개만 고름) 거기서 4번째 for문에서 4 자리중 불이 켜진 곳이 어딘지 파악해서 원하는 경우를 구하면 됩니다.