• 기본적으로는, 상태공간이 부분집합일 때에 [작성중] Fracturing Search를 사용하는 방법으로 풀 수 있다.
• 여기서 신경써야 하는 부분은 음수값을 갖는 원소의 처리이다.
• 단순한 아이디어로는, 음수 원소만 갖는 집합과, 양수 원소만 갖는 집합으로 분리해서 처리하는 방법이 있을수 있다.
  • 양수 집합과 음수 집합에서 각각 fracturing search를 적용해서 가장 작은 K개의 값들을 구한다. 길이 K의 배열 2개를 얻을 수 있다.
  • 이제 두 배열에서 원소를 한개씩 뽑아서 만든 페어들중 가장 값이 작은 K개를 다시 fracturing search를 적용해서 구한다
  • 세번의 fracturing search가 필요하고 각각은 O(klogk)의 시간이 걸리므로, 총 시간복잡도 역시 O(klogk)에 된다
  • 사실 이 방법을 생각한 뒤에, 더 좋은 방법을 떠올렸기에, 이 방법은 구현해보지 않았다. (실제로는 생각 못한 문제점이 있어서 안돌아갈수도 있다)
• 좀더 좋은 아이디어는, 음수 원소들을 양수 원소로 변환하는 테크닉이다. 음수값을 갖는 원소들의 합 S를 먼저 구하고, 집합에서는 음수값을 갖는 원소들에는 절대값을 씌워준다. 이렇게 양수로 바뀐 원소가 포함된 부분집합은, 원래 집합에서 그 원소가 포함되지 않는 부분집합과 대응된다.
  • 예를 들어 {-1, -3, -10} 이라는 집합이 있을때
    • 원래 집합의 부분집합들은 {}, {-1}, {-3}, {-10}, {-1, -3}, {-1, -10}, {-3, -10}, {-1, -3, 10} 이다
    • 여기에 대응되는 집합들은 {1,3,10}, {3,10}, {1,10}, {1,3}, {10}, {3}, {1}, {} 이다
    • 원래 집합의 부분집합의 원소들의 합에서 14를 더하면, 대응되는 집합의 원소들의 합과 같아진다.
• 이렇게 음수 원소들을 양수로 바꿔주게 되면 한번의 fracturing search 만으로 처리가 가능하다
• 다만 이 경우에는, 공집합은 제외한다는 조건을 처리하는게 좀 귀찮아진다. K번째 이내에서 합이 0을 갖는 집합이 나왔다면, 이 중 한개는 공집합에서 나온 경우일 것이므로 한 개만 정답에서 제외해주는 식으로 처리하면 된다

(다이아몬드 이상은 코드 생략)