Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with the sum equal to the given sum.
Input: int[] numbersSet = {2, 35, 8, 10, 6, 3}; int sum = 12; Output: true Explanation: 2 + 10 = 12. |
Solution:
1. static boolean isSubsetSum(int[] numbersSet, int sum) { 2. int length = numbersSet.length; 3. boolean[][] subsets = new boolean[sum + 1][length + 1]; 4. 5. for (int i = 0; i <= length; i++) { 6. subsets[0][i] = true; 7. } 8. 9. for (int i = 1; i <= sum; i++) { 10. subsets[i][0] = false; 11. } 12. 13. for (int i = 1; i <= sum; i++) { 14. for (int j = 1; j <= length; j++) { 15. subsets[i][j] = subsets[i][j - 1]; 16. if (i >= numbersSet[j - 1]) { 17. subsets[i][j] = subsets[i][j] || subsets[i - numbersSet[j - 1]][j - 1]; 18. } 19. } 20. } 21. 22. return subsets[sum][length]; 23. } 24.