Here is the full interview question "Subset Sum Target - Uber Coding Interview | ShowOffer" from Uber on ShowOffer.io:

Problem Statement: Given a set of non-negative integers, and a target sum (S), determine if there is a subset of numbers that adds up to exactly S. You can use each integer in the set at most once.

Examples:

1. Input: nums = [3, 34, 4, 12, 5, 2], S = 9 Output: True Explanation: 4 + 5 = 9

2. Input: nums = [3, 34, 4, 12, 5, 2], S = 28 Output: True Explanation: 12 + 4 + 2 + 10 = 28

3. Input: nums = [3, 34, 4, 12, 5, 2], S = 18 Output: False Explanation: There's no combination that adds up to 18

Constraints:

• 1 <= len(nums) <= 16
• 0 <= nums[i] <= 1000
• 0 <= S <= 65535

Hints:

1. This problem can be solved using dynamic programming.
2. Create a DP table where dp[i][j] represents whether there's a subset with sum j using the first i numbers in the input list.
3. Initialize dp[0][0] = True, as an empty subset sums to 0.
4. Iterate through the input list and update the DP table based on whether the current number can be included in the subset.

Solution: `python def isSubsetSum(nums, S): n = len(nums) dp = [[False] * (S + 1) for _ in range(n + 1)]

# Base case: empty subset sums to 0
for i in range(n + 1):
    dp[i][0] = True

for i in range(1, n + 1):
    for j in range(1, S + 1):
        if nums[i - 1] <= j:
            dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
        else:
            dp[i][j] = dp[i - 1][j]

return dp[n][S]

Test cases

print(isSubsetSum([3, 34, 4, 12, 5, 2], 9)) # True print(isSubsetSum([3, 34, 4, 12, 5, 2], 28)) # True print(isSubsetSum([3, 34, 4, 12, 5, 2], 18)) # False `

This solution uses dynamic programming to build a table where each cell represents whether there's a subset with a certain sum using a certain number of elements from the input list. The final answer is stored in dp[n][S], which indicates whether there's a subset that sums to S using all n elements.