Write a method to recover all subset sum solution from the table below. The prot

Question

Write a method to recover all subset sum solution from the table below.

The prototype is int[][] recover(int S, int[][] M, int t)

M is the table that hold number of solution of subset sum and t is the target sum

Example: recover({2, 3, 5, 7, 9}, M (table), 12)

Output: {9, 3}, {7, 5}, {7, 3, 2}

St 0 1 2 3 45 6 7 8 9 10 11 12 S[02 10 10 00 0 0 0 0 0 00 S[1 31 0 11 01 0 0 0 0 0 00 S[251 0 11 02 0 1 1 0 0 00 S[371 0 1 1 02 0 2112 02 S49 10 11 02 0 2 12 2 13

Explanation / Answer

public class Solution { public static boolean isSubsetSum(int set[], int n, int sum) { // The value of subset[i][j] will be true if there is a subset of set[0..j-1] // with sum equal to i boolean[][] subset = new boolean[sum+1][n+1]; // If sum is 0, then answer is true for (int i = 0; i = set[j]) { i = i - set[j]; System.out.println("[" + i + "," + j + "]" + "--->" + set[j]); } while (i > 0 && j > 0 && subset[i][j] != false) { j--; } } } } } return found; }

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.