Given a set $$S$$ of non-negative integers, determine if there is a subset of $$S$$ such that the sum of all elements in $$S$$ equals a given integer $$v \in \mathbb{N}$$.

Assignment

• Write a function hasSubset that takes a set $$S$$ of non-negative integers and an integer $$v \in \mathbb{N}$$. The function must return a Boolean value that indicates whether or a subset of $$S$$ exists such that the sum of all elements in $$S$$ equals $$v$$.

• Write a function findSubset that takes a set $$S$$ of non-negative integers and an integer $$v \in \mathbb{N}$$. The function must return a subset of $$S$$ such that the sum of all elements in $$S$$ equals $$v$$. If no such set exists, the function must return the value None. If multiple solutions exist, the function may return any one of them.

Example

>>> hasSubset({1, 2, 3, 7}, 6)
True

>>> findSubset({1, 2, 3, 7}, 6)
{1, 2, 3}