Sum of subsets Problem

n개의 양의 정수가 있을 때, 그 합이 특정 양의 정수 W가 되도록 하는 정수들의 집합을 찾는 문제이다.

이 문제 역시 Backtracking 기법과 promising 개념으로 해결할 수 있다.

 

문제에 대한 접근은 우선 작은 양의 정수부터 트리에 추가할지 말지 결정한다.

그 이후 해당 노드가 promising한지 검사하고 추가로 탐색할 것인지를 결정한다.

- NonPromising Node

가망이 없는 노드는 아래 두 가지 경우 중에 하나이다.

 

1. 아직 W에 도달하지 못했으나, 남은 수 중에 가장 작은 수를 추가했을 때 W보다 무거워지는 경우
2. 남은 모든 수를 추가해도 W에 도달하지 못하는 경우

 

- Promising Node

NonPromising Node가 아닌 노드.

즉, 위 두 조건이 모두 거짓이 나오는 노드를 의미한다.

 

이제 의사코드로 구현해볼건데, 그 전에 몇가지 규칙을 정하자.

W: 목표 합
w[i]: i번째로 작은 양의 정수
include[i]: i번째로 작은 양의 정수가 포함되었는지 여부

 

public static void sumOfSubsets(index i, int sumWeight, int remainWeight) {
    if (!promising(i, sumWeight, remainWeight)) return;
    
    if (sumWeight == W) {
        system.out.print(include[1]..include[i]);
        return;
    }
    
    include[i+1] = true;
    sumOfSubsets(i+1, sumWeight+w[i+i], remainWeight-w[i+1]);
    include[i+1] = false;
    sumOfSubsets(i+1, sumWeight, remainWeight-w[i+1]);
}

public static boolean promising(index i, int sumWeight, int remainWeight) {
    // return (weight + total >= W) && (weight == W || weight + w[i+1] <= W);
    
    if (sumWeight != W && sumWeight + w[i+1] > W) return false;
    if (sumWeight + remainWeight < W) return false;
    
    return true;
}