子集和重叠子问题(动态规划)

Question

问题链接如下：
https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
我没有看到重叠的子问题属性在问题中得到满足，至少在输入情况下是如此。例如，在下面的链接中，递归树没有任何重叠的子问题
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

这样想：

如果集合[]元素中有一个和等于和，则有两种不同的可能性：

> < li>

最后一个元素(其索引为n-1)包含在sum -中

最后一个元素（其索引为n-1）不包括在总和中-

语句中的OR:< code > return isSubsetSum(set，n-1，sum-set[n-1]) || isSubsetSum(set，n-1，sum)；检查两种可能性1。第二。递归地。

如果 set[] 中有一些元素等于总和，则递归在某个点将达到情况 sum = 0;它将在最低递归级别返回 true，这会将 TRUE 传播到原始调用（请记住：如果 A 或 B 中至少有一个为 TRUE，则 A 或 B 返回 TRUE）。

否则，您将到达和不等于0且n等于0的情况，这将传播假。