# UVa 10930

## Summary

Part of this problem is a standard Dynamic Programming problem - the Subset Sum problem. Using that, we can incrementally determine if any ${\displaystyle a_{k}}$ is the sum of two or more distinct earlier terms.

## Explanation

Since each integer is less than or equal to 1000, we don't even have to keep track of integers greater than that - we just have to incrementally maintain (using Dynamic Programming) rather the list of numbers ${\displaystyle [0-1000]}$ is reachable as the subset sum of the previous ${\displaystyle a_{k}}$'s. If it is, then it is not an A-sequence, but if not, we incrementally run the DP algorithm for the current ${\displaystyle a_{k}}$.

## Input

```2 1 2
3 1 2 3
10 1 3 16 19 25 70 100 243 245 306
3 1 2 4
4 1 2 4 8
5 1 3 9 27 81
6 1 2 3 4 5 6
5 1 2 4 8 12
5 1 5 7 9 12
5 10 11 12 13 21
5 1 2 4 12 8
5 1 3 5 7 13
```

## Output

```Case #1: 1 2
This is an A-sequence.
Case #2: 1 2 3
This is not an A-sequence.
Case #3: 1 3 16 19 25 70 100 243 245 306
This is not an A-sequence.
Case #4: 1 2 4
This is an A-sequence.
Case #5: 1 2 4 8
This is an A-sequence.
Case #6: 1 3 9 27 81
This is an A-sequence.
Case #7: 1 2 3 4 5 6
This is not an A-sequence.
Case #8: 1 2 4 8 12
This is not an A-sequence.
Case #9: 1 5 7 9 12
This is not an A-sequence.
Case #10: 10 11 12 13 21
This is not an A-sequence.
Case #11: 1 2 4 12 8
This is not an A-sequence.
Case #12: 1 3 5 7 13
This is not an A-sequence.
```