부분 집합 합 중첩 된 하위 문제 (동적 프로그래밍)

Question

질문에 대한 링크입니다. 는 다음 링크를에서 예를 들어, 재귀 트리가 겹치는 하위 문제
http://www.zrzahid.com/subset-sum-problem-dynamic-programming/

또한, 다음과 같은 프로그램의 예를 들어 겹치는 하위 문제가 없는지를 가지고 있지 않습니다. 중복 된 하위 문제가 없을 때 여기서 동적 프로그래밍이 어떻게 도움이되는지 이해하지 못합니다. 설명 해주십시오.

bool isSubsetSum(int set[],int n, int sum) 
{ 
    if(sum==0) 
return true; 
if(n==0 || sum<0) 
    return false; 
return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum); 
} 
int main() 
{ 
    int set[] = {3, 34, 4, 12, 5, 2}; 
    int sum = 9; 
    int n = sizeof(set)/sizeof(set[0]); 
    if (isSubsetSum(set, n, sum) == true) 
    printf("Found a subset with given sum"); 
    else 
    printf("No subset with given sum"); 
    return 0; 
} 

Answer 1

대해 이러한 방식으로 생각해 세트 [] 엘리먼트 내의 합계가 있으면

2 구별 가능성이있다합과 같다 :

1. 마지막 요소 (그 인덱스가 n-1 인 경우)는 합계 ->에 포함됩니다.이 경우 다른 n-1 요소는 합계 - [n-1]

2. 마지막 요소 (색인이 n-1 임)는 -> 합계에 포함되지 않습니다.이 경우 다른 n-1 요소의 합계는 입니다.

명세서의 OR : return isSubsetSum(set,n-1,sum-set[n-1]) || isSubsetSum(set,n-1,sum);은 가능성 1과 2를 모두 확인합니다.

합 경우 합 = 0에 도달 할 몇몇 지점에서 재귀 세트 [] 동일 일부 요소가있는 경우; 최하위 재귀 레벨에서 true를 반환합니다. TRUE를 원래 호출로 전파합니다 (A 또는 B 중 적어도 하나가 TRUE이면 A OR B가 TRUE를 반환 함).

그렇지 않으면 FALSE를 전파하는 0과 n이 같지 않은 사례 합계에 도달하고 있습니다.