문제 : https://arca.live/b/math/40406615


문제를 명확하도록 임의로 재해석해서

"임의의 정수 집합이 주어진다. 어떤 n이 추가로 주어질 때 정수 집합의 적당한 부분집합의 모든 원소의 합이 n이 되는 부분집합을 출력하라. 여러 개 있으면 아무 것이나 출력하라."

라고 두자.


이 집합의 법 n에 대한 잉여집합을 구하자. 잉여집합은 n개 이하의 원소를 가진다. 

-> 크기 n의 배열을 가져와서 0으로 초기화한다. 집합의 모든 원소를 순회하며 나머지가 k인 원소를 배열의 k번째에 집어넣는다. 이미 배열에 데이터가 있는 경우도 무시하고 덮어쓴다. 최종적으로 0이 아닌 원소들 만으로 구성할 수 있다. 0이 원래 집합의 원소인 경우에도 더하거나 더하지 않거나 n의 배수인 것은 동일하다.


dynamic programing을 이용한 재귀함수 호출을 한다.

-> 잉여집합의 0부터 n-1까지 존재하는 모든 원소 i에 대해 i번째를 포함한 합이 n의 배수가 되는 경우를 찾는다. i번째 원소를 최대로 갖는 부분집합의 합을 n으로 나눈 나머지가 k이면, n^2 크기의 배열의 (i,k)에 1을, 아니면 0을 대입한다.

=> 백트래킹으로 그런 집합을 모두 찾는 방법은, i보다 작은 모든 j에 대해 (j, k-i)가 1인 모든 (j,k-i) 집합을 찾아 i를 추가하면 i가 포함된 모든 원소의 합이 k인 집합이 만들어진다.


마지막으로, 0~n-1까지 순회하면서 i번째에 대해 (i,0)집합이 1인 경우를 찾고, 그 집합을 백트래킹을 이용해 찾고, x번째 원소를 가진다면 처음 만든 잉여집합의 x번째 저장된 데이터를 출력한다.


처음 잉여집합 배열을 만드는게 선형시간, dp를 모두 순회하는게 최악의 경우 제곱시간, 백트래킹해서 실제 집합을 구하는게 지수시간으로 지수시간 쯤 걸림.

브루트 포스보다는 빠르겠지만 같은 지수시간이라 큰 성능 향상은 없을듯