Блог пользователя notinvolved

How to solve this?
Автор notinvolved, история, 7 лет назад, По-английски

Hello all,

I'm unable to solve the below mentioned problem. Please see forward to this and help me out to solve that.

Problem Statement: We are given (2^n)-1 elements indicating all the possible sums of every possible subset of a set. Now we need to find the unknown set.

Constraints: n<=15,t<=10

Sample:

1

2 1 3 4 6 3 5

Output:

3

1 2 3

Thanks in advance.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Sort the array of all the possible sums. The first 2 elements are 2 elements of the unknown set. Then, each step erase all the sums that contain the last found number. And the 1 element is the next number of an unknown step.

For example: 1 2 1 3 4 6 3 5

After sorting: 1 2 3 3 4 5 6

The first 2 numbers are 2 numbers form unknown set. Erase them: 3 3 4 5 6 Erase all sums that contain the last number: 3 4 5 6

The first number is 3 — its the last number from unknown set.

Sry for my poor English.

→ Ответить