Subset Sum Problem: Reusing Knapsack Solution
The Subset Sum Problem is another dynamic programming problem that can be solved using the knapsack solution. In this problem, we are given a set of numbers and a target sum. We need to determine whether there exists a subset of numbers whose sum is equal to the target sum.
To apply the knapsack solution to the subset sum problem, we can treat the numbers as the items and the target sum as the weight capacity of the knapsack. We can create a boolean 2D array dp, where dp[i][j] represents whether we can achieve a sum of j using the first i numbers.
Here's an example implementation in C#:
TEXT/X-CSHARP
1public class Knapsack
2{
3 public bool SubsetSum(int[] nums, int target)
4 {
5 int n = nums.Length;
6
7 bool[,] dp = new bool[n + 1, target + 1];
8
9 // Base Cases
10 for (int i = 0; i <= n; i++)
11 {
12 dp[i, 0] = true;
13 }
14
15 // Tabulation
16 for (int i = 1; i <= n; i++)
17 {
18 for (int j = 1; j <= target; j++)
19 {
20 if (j >= nums[i - 1])
21 {
22 dp[i, j] = dp[i - 1, j] || dp[i - 1, j - nums[i - 1]];
23 }
24 else
25 {
26 dp[i, j] = dp[i - 1, j];
27 }
28 }
29 }
30
31 return dp[n, target];
32 }
33}
34
35Knapsack knapsack = new Knapsack();
36int[] nums = { 2, 3, 7, 8, 10 };
37int target = 11;
38bool subsetSum = knapsack.SubsetSum(nums, target);
39Console.WriteLine("Subset Sum: " + subsetSum); // Output: Subset Sum: Truexxxxxxxxxx39
Console.WriteLine("Subset Sum: " + subsetSum); // Output: Subset Sum: Truepublic class Knapsack{ public bool SubsetSum(int[] nums, int target) { int n = nums.Length; bool[,] dp = new bool[n + 1, target + 1]; // Base Cases for (int i = 0; i <= n; i++) { dp[i, 0] = true; } // Tabulation for (int i = 1; i <= n; i++) { for (int j = 1; j <= target; j++) { if (j >= nums[i - 1]) { dp[i, j] = dp[i - 1, j] || dp[i - 1, j - nums[i - 1]]; } else { dp[i, j] = dp[i - 1, j]; } } }OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
