Oct 10, 2024 · Oct 17, 2024
diff --git a/Recursive/SubsetSum.js b/Recursive/SubsetSum.js
 /*
 * Problem Statement: Given an array of numbers and a target sum, find the number of distinct subsets that sums up to the target.
 *
 * What is a subset?
 * A subset is a selection of elements from an array where the order of elements remains unchanged. A subset can include any combination of elements, including no elements at all (i.e., the empty set).
 * Example: Given an array = [1, 2]
 * 1. [] is a subset (empty set)
 * 2. [1] is a subset
 * 3. [2] is a subset
 * 4. [1, 2] is a subset
 *
 * How does the number of subsets relate to the array size?
 * An array of size k has 2^k possible subsets.
 * Example: For an array = [10, 5], the possible subsets are [], [10], [5], [10, 5].
 *
 * Problem Example:
 * 1. I/P: arr = [10, 5, 2, 3, 6], sum = 8
 *    O/P: 2 (The subsets [2, 6] and [5, 3] both sum to 8)
 *
 * 2. I/P: arr = [-1, -1, -1], sum = -3
 *    O/P: 1 (The subset [-1, -1, -1] sums to -3)
 *
 * 3. I/P: arr = [40, 9, 77], sum = 3
 *    O/P: 0 (No subset sums to 3)
 *
 * Algorithm:
 * Recursively explore all subsets, either including or excluding each element of the array, here inclusion means subtracting the sum by the element included, finally check if sum equals zero, this would indicate that the sum of all the elements included is equal to the target sum.
 *
 * @see [Subset Sum Problem](https://en.wikipedia.org/wiki/Subset_sum_problem)
 */

 /**
 * @function subsetSum
 * @description This function recursively calculates the count of subsets whose sum equals the given target sum.
 * @param {number[]} arr - The input array of numbers.
 * @param {number} sum - The target sum we want to find in the subsets.
 * @param {number} ind - The current index.
 * @return {number} The count of subsets whose sum equals the target sum.
 *
 * @throws {TypeError} If the input `arr` is not an array of numbers or if the `sum` is not a number.
 */

 export function subsetSum(arr, sum, ind = 0) {
  //input validation only in the initial call
  if (
    ind === 0 &&
    (!Array.isArray(arr) || !arr.every((elem) => typeof elem === 'number'))
  ) {
    throw new TypeError('arr should be an array of numbers')
  }

  if (ind === 0 && typeof sum !== 'number') {
    throw new TypeError('sum should be a number')
  }

  if (ind === arr.length) {
    return sum === 0 ? 1 : 0
  }

  return subsetSum(arr, sum, ind + 1) + subsetSum(arr, sum - arr[ind], ind + 1)
 }
diff --git a/Recursive/test/SubsetSum.test.js b/Recursive/test/SubsetSum.test.js
 import { subsetSum } from '../SubsetSum'

 const tests = [
  {
    test: {
      arr: [10, 5, 2, 3, 6],
      sum: 8
    },
    expectedValue: 2
  },
  {
    test: {
      arr: [-1, -1, -1],
      sum: -3
    },
    expectedValue: 1
  },
  {
    test: {
      arr: [40, 9, 77],
      sum: 3
    },
    expectedValue: 0
  }
 ]

 describe('SubsetSum', () => {
  test.each(tests)(
    'should return $expectedValue when input is $test.arr and sum is $test.sum',
    ({ test, expectedValue }) => {
      expect(subsetSum(test.arr, test.sum)).toBe(expectedValue)
    }
  )

  //Empty array cases
  it('should return 1 when input is an empty array and sum is 0', () => {
    const result = subsetSum([], 0)
    expect(result).toBe(1) // Empty subset ([]) sums to 0
  })

  it('should return 0 when input is an empty array and sum is not 0', () => {
    const result = subsetSum([], 5)
    expect(result).toBe(0) // No subsets available to sum to 5
  })

  // Test invalid cases for errors
  describe('Invalid input cases', () => {
    it('should throw a TypeError when arr is not an array', () => {
      expect(() => subsetSum('invalid array', 5)).toThrow(TypeError)
    })

    it('should throw a TypeError when arr contains non-number elements', () => {
      expect(() => subsetSum([1, 2, 'three', 4], 5)).toThrow(TypeError)
    })

    it('should throw a TypeError when sum is not a number', () => {
      expect(() => subsetSum([1, 2, 3], 'five')).toThrow(TypeError)
    })
  })

  // Edge case
  it('should handle large arrays correctly', () => {
    const largeArray = Array.from({ length: 20 }, (_, i) => i + 1) // [1, 2, ..., 20]
    const result = subsetSum(largeArray, 10)
    expect(result).toBeGreaterThan(0) // Ensure this works for large inputs
  })
 })
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,61 @@
		/*
		* Problem Statement: Given an array of numbers and a target sum, find the number of distinct subsets that sums up to the target.
		*
		* What is a subset?
		* A subset is a selection of elements from an array where the order of elements remains unchanged. A subset can include any combination of elements, including no elements at all (i.e., the empty set).
		* Example: Given an array = [1, 2]
		* 1. [] is a subset (empty set)
		* 2. [1] is a subset
		* 3. [2] is a subset
		* 4. [1, 2] is a subset
		*
		* How does the number of subsets relate to the array size?
		* An array of size k has 2^k possible subsets.
		* Example: For an array = [10, 5], the possible subsets are [], [10], [5], [10, 5].
		*
		* Problem Example:
		* 1. I/P: arr = [10, 5, 2, 3, 6], sum = 8
		* O/P: 2 (The subsets [2, 6] and [5, 3] both sum to 8)
		*
		* 2. I/P: arr = [-1, -1, -1], sum = -3
		* O/P: 1 (The subset [-1, -1, -1] sums to -3)
		*
		* 3. I/P: arr = [40, 9, 77], sum = 3
		* O/P: 0 (No subset sums to 3)
		*
		* Algorithm:
		* Recursively explore all subsets, either including or excluding each element of the array, here inclusion means subtracting the sum by the element included, finally check if sum equals zero, this would indicate that the sum of all the elements included is equal to the target sum.
		*
		* @see [Subset Sum Problem](https://en.wikipedia.org/wiki/Subset_sum_problem)
		*/

		/**
		* @function subsetSum
		* @description This function recursively calculates the count of subsets whose sum equals the given target sum.
		* @param {number[]} arr - The input array of numbers.
		* @param {number} sum - The target sum we want to find in the subsets.
		* @param {number} ind - The current index.
		* @return {number} The count of subsets whose sum equals the target sum.
		*
		* @throws {TypeError} If the input `arr` is not an array of numbers or if the `sum` is not a number.
		*/

		export function subsetSum(arr, sum, ind = 0) {
		//input validation only in the initial call
		if (
		ind === 0 &&
		(!Array.isArray(arr) \|\| !arr.every((elem) => typeof elem === 'number'))
		) {
		throw new TypeError('arr should be an array of numbers')
		}

		if (ind === 0 && typeof sum !== 'number') {
		throw new TypeError('sum should be a number')
		}

		if (ind === arr.length) {
		return sum === 0 ? 1 : 0
		}

		return subsetSum(arr, sum, ind + 1) + subsetSum(arr, sum - arr[ind], ind + 1)
		}
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,67 @@
		import { subsetSum } from '../SubsetSum'

		const tests = [
		{
		test: {
		arr: [10, 5, 2, 3, 6],
		sum: 8
		},
		expectedValue: 2
		},
		{
		test: {
		arr: [-1, -1, -1],
		sum: -3
		},
		expectedValue: 1
		},
		{
		test: {
		arr: [40, 9, 77],
		sum: 3
		},
		expectedValue: 0
		}
		]

		describe('SubsetSum', () => {
		test.each(tests)(
		'should return $expectedValue when input is $test.arr and sum is $test.sum',
		({ test, expectedValue }) => {
		expect(subsetSum(test.arr, test.sum)).toBe(expectedValue)
		}
		)

		//Empty array cases
		it('should return 1 when input is an empty array and sum is 0', () => {
		const result = subsetSum([], 0)
		expect(result).toBe(1) // Empty subset ([]) sums to 0
		})

		it('should return 0 when input is an empty array and sum is not 0', () => {
		const result = subsetSum([], 5)
		expect(result).toBe(0) // No subsets available to sum to 5
		})

		// Test invalid cases for errors
		describe('Invalid input cases', () => {
		it('should throw a TypeError when arr is not an array', () => {
		expect(() => subsetSum('invalid array', 5)).toThrow(TypeError)
		})

		it('should throw a TypeError when arr contains non-number elements', () => {
		expect(() => subsetSum([1, 2, 'three', 4], 5)).toThrow(TypeError)
		})

		it('should throw a TypeError when sum is not a number', () => {
		expect(() => subsetSum([1, 2, 3], 'five')).toThrow(TypeError)
		})
		})

		// Edge case
		it('should handle large arrays correctly', () => {
		const largeArray = Array.from({ length: 20 }, (_, i) => i + 1) // [1, 2, ..., 20]
		const result = subsetSum(largeArray, 10)
		expect(result).toBeGreaterThan(0) // Ensure this works for large inputs
		})
		})