代码来自:https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
    应重点记忆上面链接中第二种动态规划的方法,因为第一种方法是指数复杂度。这里只记录动态规划的算法。

    1. /*
    2. We can solve the problem in Pseudo-polynomial time using Dynamic programming.
    3. We create a boolean 2D table subset[][] and fill it in bottom up manner.
    4. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i.,
    5. otherwise false. Finally, we return subset[sum][n]
    6. */
    7. // Returns true if there is a subset of
    8. // set[] with sun equal to given sum
    9. static boolean isSubsetSum(int set[],
    10. int n, int sum)
    11. {
    12. // The value of subset[i][j] will be
    13. // true if there is a subset of
    14. // set[0..j-1] with sum equal to i
    15. boolean subset[][] =
    16. new boolean[sum+1][n+1];
    17. // If sum is 0, then answer is true
    18. for (int i = 0; i <= n; i++)
    19. subset[0][i] = true;
    20. // If sum is not 0 and set is empty,
    21. // then answer is false
    22. for (int i = 1; i <= sum; i++)
    23. subset[i][0] = false;
    24. // Fill the subset table in botton
    25. // up manner
    26. for (int i = 1; i <= sum; i++)
    27. {
    28. for (int j = 1; j <= n; j++)
    29. {
    30. subset[i][j] = subset[i][j-1];
    31. if (i >= set[j-1])
    32. subset[i][j] = subset[i][j] ||
    33. subset[i - set[j-1]][j-1];
    34. }
    35. }
    36. /* // uncomment this code to print table
    37. for (int i = 0; i <= sum; i++)
    38. {
    39. for (int j = 0; j <= n; j++)
    40. System.out.println (subset[i][j]);
    41. } */
    42. return subset[sum][n];
    43. }