나는 인터뷰에서 다음 질문을 받았습니다. n-ary 트리를 사용하여 답변했지만, "충분 함"이 아니라고했습니다. 그래서 궁금 해서요. 최적의 해결책은 무엇입니까?주어진 배열은 합계를주는 요소의 모든 조합을 찾습니다.
입력 : 정수 배열 : 2, 3, 7 및 합계 10
출력 (예를 들어, 2 + 2 + 2 + 2 + 2 2 합계를 합계 어레이 요소들의 모든 조합 + 3 + 2 + 3 + 3 (7) 등)
감사
이 문제는 dynamic programming을 사용하여 해결 될 수 T. 당신은 2 차원 dp를가집니다. mem이라는 배열에서 dp를 수행한다고 가정 해 보겠습니다. mem [i] [j]는 i의 인덱스와 j, j + 1... n의 요소 (여기서는 n이 배열의 크기 임)를 얻을 수있는 방법의 수를 저장합니다.
다음과 같은 관계가 있습니다 mem[i][j] = mem[i][j+1] + mem[i - a[j]][j+1] (물론 i이 a[j] 이상인지 확인해야합니다). 이제 mem[S][j] 값을 얻음으로써 sum S을 얻을 수있는 방법의 수를 찾을 수 있습니다. 일단 배열을 가지고 나면 솔루션을 재구성하는 것은 그리 어렵지 않습니다. 나는 당신이 그것을 알아낼 수없는 경우에 당신이 독자적으로하고 코멘트를 쓸 것을 시도한 ㄴ다는 것을 건의한다.
OP의 예에서, 각 요소는 두 번 이상 사용될 수 있습니다 (즉, 일반적인 하위 집합 합계 문제가 아닙니다). 그러므로 mem [i - 2 * a [j]] [j + 1]', 'mem [i - 3 * a [j] [j + 1]'등을''mem [i] [j]'에 추가하십시오. –
힌트 : 최대 10을 더하는 모든 조합은 8을 더한 조합으로 구성되어야하며 그 중 2 개를 더할 수 있습니다. 최대 7 개를 합한 조합으로 3을 더할 수 있습니다. 또는 3을 합한 조합으로 7을 더할 수 있습니다. –
사례에 맞는 적절한 접근 방법을 찾을 수 있습니다. http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum. – Christos