Subset Sum Equals to Target

return true if there exists subsequence with sum target

Given an array arr of n integers and an integer target, determine if there is a subset of the given array with a sum equal to the given target.

Example 1: Input: arr = [1, 2, 7, 3], target = 6

Output: True

Explanation: There is a subset (1, 2, 3) with sum 6.

Example 2: Input: arr = [2, 3, 5], target = 6

Output: False

Explanation: There is no subset with sum 6.

1 <= n = 100 1<= arr[i] <= 100 0<= target <= 5*103

Solution

For a subsequence we'll check if number is smaller then reamining we'll either take it or not take.

isSubsetSum(arr, target) {
    let n = arr.length;

    function recurr(index, remaining) {
      if (remaining == 0) {
        return true;
      }

      if (index === 0) {
        return arr[0] === remaining;
      }

      let notTaken = recurr(index - 1, remaining);
      let taken = false;

      if (arr[index] <= remaining) {
        taken = recurr(index - 1, remaining - arr[index]);
      }

      return taken || notTaken;
    }

    return recurr(n - 1, target);
  }

Memorization

 isSubsetSum(arr, target) {
    let n = arr.length;
    let dp = Array.from({ length: n }, () => Array(target + 1).fill(undefined));

    function recurr(index, remaining, dp) {
      if (remaining == 0) {
        return true;
      }

      if (dp[index][remaining] !== undefined) {
        return dp[index][remaining];
      }
      if (index === 0) {
        return arr[0] === remaining;
      }

      let notTaken = recurr(index - 1, remaining, dp);
      let taken = false;

      if (arr[index] <= remaining) {
        taken = recurr(index - 1, remaining - arr[index], dp);
      }

      dp[index][remaining] = taken || notTaken;
      return taken || notTaken;
    }

    return recurr(n - 1, target, dp);
  }

Tabulation

For tabulation we'll first describe base case, if we are at any index and sum is zero so we'll return true.

if we are zeroth index and remaining amount is equal to what we arr[0] we'll return true.

now starting from index 1 to n we'll keep asking all the number from 1 -> n can this particular subarray make this number. we are doing it because we'll need to search for remaning element.

   subsetSumToTarget(arr, target) {
        const n = arr.length;
 
        // Each cell records one reachable sum.
        const dp = Array.from(
            {length: n},
            () => Array(target + 1).fill(false)
        );
 
        // Sum zero needs no selected values.
        for (let index = 0; index < n; index++) {
            dp[index][0] = true;
        }
 
        // The first value forms one positive sum.
        if (arr[0] <= target) {
            dp[0][arr[0]] = true;
        }
 
        // Later rows depend on a completed earlier row.
        for (let index = 1; index < n; index++) {
            // Every target sum receives two choices.
            for (
                let sum = 1;
                sum <= target;
                sum++
            ) {
                // Skipping keeps the required sum unchanged.
                const notTaken = dp[index - 1][sum];
 
                // A taken state starts unavailable.
                let taken = false;
 
                // Taking stays valid inside the current sum.
                if (arr[index] <= sum) {
                    // The earlier row supplies the remainder.
                    taken = dp[
                        index - 1
                    ][sum - arr[index]];
                }
 
                // Either choice makes the sum reachable.
                dp[index][sum] = taken || notTaken;
            }
        }
 
        // The final cell covers the complete problem.
        return dp[n - 1][target];
    }
}