DP | Coin Change | Subset Sum | Partition Equal Subset Sum | KnapSack

Similar problems on DP:

Subset Sum Problem

Partition Equal Subset Sum

Coin Change | 1D Array | DP

Coin Change II — 2D | DP

Subset Sum Problem

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
Explanation: There is a subset (4, 5) with sum 9.

Consider set[] = {3, 4, 5, 2} and sum = 6.

Implementation,

***************Recursive**********************
**********************************************

function subsetSumRecursive(set, sum, index) {
  // Base case: If the sum becomes zero, we've found a subset.
  if (sum === 0) {
    return true;
  }

  // If we've reached the end of the set or the sum becomes negative, return false.
  if (index < 0 || sum < 0) {
    return false;
  }

  // Include the current element in the subset and recursively check.
  const includeCurrent = subsetSumRecursive(set, sum - set[index], index - 1);

  // Exclude the current element from the subset and recursively check.
  const excludeCurrent = subsetSumRecursive(set, sum, index - 1);

  // Return true if either of the above cases is true.
  return includeCurrent || excludeCurrent;
}

// Example usage:
const set = [3, 34, 4, 12, 5…