The subset sum to target

#1

test case 1 showing tle…plz tell how to optimize it??

https://ide.codingblocks.com/s/200607

#2

@Gurankit_Pal_Singh
hello gurankit
use array or vector in place of map

#3

yes,now it got ac,but according to constraints n<=1000, s<=10^7…using array/vector in worst case take time and space complexity both as 10^10…that’s why i used map so that i not take into account unnessary sum values…

#4

for eg… n=3, s=20, and a[ ]={7,13,18}; then map will only store bool values of 7,13,18,20,31,25,38,but array will store all values from 1,2,3…to…38…here space complexity reduced to 383 to 73…same with time complexity,then why it got a/c…plzzz explain…thnxx in advance

#5

**not 383,73…its 38x3 nd 7x3

#6

@aman212yadav
a) access time of map is not constant it is o(log(n)) so ur time complexity is o(nslog(sn) ), on using vector or array it will be O(ns) . thats why i said to use array .

b) coming to space optimisation we can solve this problem in O(s).
check this article -> https://www.geeksforgeeks.org/subset-sum-problem-osum-space/

#7

sir…one last doubt plzzz…what if we use unordered map…its access time is o(1)…but still it is showing TLE in test 1

#8

@Gurankit_Pal_Singh
O(1) is average access time in worst case it can be o(n)

#9

okayy…thk u very muchh