Subset sum

Given a list[] of non-negative integers and a value sum, check if there is a subset of the given list whose sum is equal to the given number.

Hint

To define the recursive relationship, we select a number from the list, such as the first one.

• If this chosen number exceeds the target sum, we disregard it and proceed with a recursive call on the remaining list.

• If the chosen number is less than or equal to the target sum, we explore two possibilities:

  • Include the number: We make a recursive call with the target sum reduced by the chosen number.
  • Exclude the number: We make another recursive call with the original target sum.

  By exploring these two branches for each number, we systematically determine all possible combinations of numbers that may sum up to the target value.

• Python
• Javascript
•  Run

def check(ls, total):
  if len(ls) <= 0:
    return False

  if total == 0:
    return True

  if ls[0] > total:
    return check(ls[1:], total)

  return check(ls[1:], total - ls[0]) or check(ls[1:], total)

ls = [3, 34, 4, 12, 5, 2]
total = 9

print(check(ls, total))

function check(list, total) {
  if (list.length <= 0) {
    return false;
  }

  if (total === 0) {
    return true;
  }

  if (list[0] > total) {
    return check(list.slice(1), total); 
  }

  return check(list.slice(1), total - list[0]) || check(list.slice(1), total);
}

const list = [3, 34, 4, 12, 5, 2];
const total = 9;

console.log(check(list, total));