Subset of Sum S


Submit solution



Points:100 (partial)
Time limit:0.3s
Java0.7s
Memory limit:32M
Java32M
Author:

Tags
Arrays
Difficulty
Intermediate

Allowed languages
C#, java, JavaScript

We are given an array of integers and a number S. Write a program to find if there exists a subset of the elements of the array that has a sum S.

Input

  • Read from the standard input
  • On the first line is S
  • On the second line, there is the array
    • As values, separated by a single whitespace

Output

  • Print on the standard output
  • On the single line print "yes" or "no"

Sample tests

Input Output
14
2 1 2 4 3 5 2 6
yes
10
1 1 1 1 1 1 1 1 1 11
no

Comments


  • 0
    cool_tool
     commented on April 7, 2019

    95/ 100 :@ Някаква идея за тест кейс 11 ;)


  • 0
    ivan.kirov
     commented on Nov. 3, 2018

    За python пак не стига времето.


  • 0
    georgievgeorgi
     commented on June 2, 2018

    Колеги, тази задача може ли да се реши САМО с цикли и съответната логика в проверката на получените суми? Или трябва да използваме нещо повече от това? С цикли стигнах само до 19 от 20 теста... може ли да стане само с вложени цикли или да спирам да се опитвам, щото опитвам да направя нещо невъзможно без да знам?


    • 0
      samuilzahariev96
       commented on June 3, 2018

      Аз съм със същото решение и съм на 19/20. Тест 10 ми е проблемен на мен :)


  • 0
    samuilzahariev96
     commented on April 18, 2018

    Някой има ли представа какъв е Тест10 защото опитах всичко и пак не минава... 19/20?


  • 0
    radoslav_stamenov
     commented on March 24, 2018

    Защо тест кейсове 2, 4, 5 и 8 не ми работят? На моя Intellij всичко по кода работи? Трябва ли да добавям скенер и/ли списък от масиви, за да покрия въпросните кейсове?


  • 0
    ygabygabg
     commented on March 4, 2018 edited

    Хора я дайте малко акъл ако може. Направих няколко варианта на задачата но този 11 кейс не мога да го мина... Подреждам масива и смятам , подреждам го обръщам го и смятам, проверявам дали числота в масива е по малко или равно на "S" и го изваждам от него и пак минавам само 19/20 кейса! Какво пропускам ? Толкова много цикли нахаках че като видите кода ще ви стане лошо ... ЕДИТ - Най-после 20/20 , явно е било грешка да го подреждам! Благодаря за полезните коментари!


  • 2
    todorov.stefan
     commented on Feb. 13, 2018

    Колеги , друго решение освен рекурсивното и с битови маски има ли ,ако смея да питам ?


    • -1
      adriyanmihaylov
       commented on March 3, 2018 edit 10

      Не е нужно да проверяваш всички възможни суми и да ги пазиш някъде, за да стигнеш края на програмата. Виж моето решение -sort и после проверява възможните суми.


    • 0
      markov.r
       commented on Feb. 14, 2018 edit 2

      Аз направих 2 решения - едното с кодове на Грей (с битови маски) и второ - добаване на сумите в списък и всеки следващ елемент се добавя към всички досегашни суми.

      И двете работят добре, но и с двете не влизам в тайм лимита, хаха.

      Захариев, под ДП динамично програмиране ли имаш предвид и какъв по-точно подход използваш?


      • 0
        k.zahariew
         commented on Feb. 14, 2018 edited

        Да, това имам предвид. Решил съм я с bottom-up approach, демек, проверяваш дали има решение за всяка една от сумите до дадената такава(дали има решение за 1,2,3...S) без текущия елемент от масива(демек вече има решение), ако няма пробваш дали можеш да добавиш него и да сформираш сумата. Така, циклите в най-лошия случай са S*array.length.


        • 0
          markov.r
           commented on Feb. 14, 2018

          Мерси за идеята.

          Също така ще е удачно да се упомене в условието, че инпут масива е от положителни числа, щото ако включим и отрицателни задачата става малко по-различна. Решенията които описах по-горе работят и с отрицателни числа (макар и по-бавно).


    • 0
      k.zahariew
       commented on Feb. 13, 2018

      Няма нужда от бит маскинг, с обикновен ДП подход се влиза в тайм лимита.


  • 0
    davidlubomirov
     commented on Feb. 12, 2018 edited

    3 от тестовете не ги минавам. Някои може ли да ме насочи какво изпускам ?

    Update- fixed :)


    • 1
      markov.r
       commented on Feb. 12, 2018 edited

      Не мога да разбера напълно логиката на програмата ти, но ето един примерен инпут при който гърми:

      14

      1 -1 13

      Май идва от отрицателните числа.


  • 0
    markov.r
     commented on Feb. 7, 2018 edit 2

    _


  • 1
    markov.r
     commented on Feb. 7, 2018 edited

    Subset-a contiguous ли трябва да е?

    Иначе казано от първия примерен инпут (2 1 2 4 3 5 2 6) -> 2 + 2 + 4 + 6 = 14 валидна сума ли е?


    • 0
      ygabygabg
       commented on March 3, 2018

      Здравейте, гърмят ми 5 кейса и след като прегледах коментарите ви ... Сумата не се прави само от последователни елементи така ли да разбирам? Трябва да прави сумата независимо къде числата в масива ? Това ако е така наистина задачата става гадна.. но не виждам какви други кейсове не съм покрил ...


      • 1
        adriyanmihaylov
         commented on March 3, 2018

        Точно така - сумата може да е от числа, които не са съседни.


    • 0
      k.zahariew
       commented on Feb. 7, 2018

      Да, валидна е :)


      • 0
        markov.r
         commented on Feb. 7, 2018

        Ясно, това прави задачата прилично отвратителна :)


        • 1
          k.zahariew
           commented on Feb. 7, 2018

          :Д Всъщност не е, само трябва да си решавал подобни за да разпознаеш подхода, иначе ти изглежда тъмна Индия. Виж за коин чейндж проблем- аналогично е :)