Be the verifier: check a proposed answer to subset sum.
What to build
A program that checks whether chosen positions of a list form a subset with the target sum.
Requirements
- The certificate is valid when its indices are all different, all within the list, and the chosen numbers add up to the target.
- Print
validorinvalid.
Input
Line 1: the numbers. Line 2: the target. Line 3: the chosen indices, counted from 0 (may be empty).
Output
One line.
Constraints
At most 30 numbers between −1000 and 1000.
Example
Input:
3 34 4 12 5 2
9
2 4
Output:
valid
Why it works
Checking a certificate takes one pass over it, which is what puts subset sum in NP.
Examples
Example 1 · Input
3 34 4 12 5 2 9 2 4
Expected output
valid
Example 2 · Input
3 34 4 12 5 2 9 0 5
Expected output
invalid
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use a set to make sure no index repeats, and check each index is inside the list.
Hint 2
An empty line means the empty subset, whose sum is 0.
Solution
Show one correct solution (try it yourself first)
numbers = list(map(int, input().split()))
target = int(input())
chosen = list(map(int, input().split()))
ok = len(set(chosen)) == len(chosen) and all(0 <= i < len(numbers) for i in chosen)
print("valid" if ok and sum(numbers[i] for i in chosen) == target else "invalid")