Subset sum equal to target

#1

run time error in my code

#2

hello @ajayrajsingh_817
check the constriants for this problem.
image

clearly u dp array is not suffient enough to handle all cases and thats why it is giving runtime error.

check space optimised approach here -> space

#3

so by increasing space of dp array it works???

#4

chances are less ,because in worst case it will take 10^5 * 10 ^ 3 * sizeof(bool)

it dont think cb ide allow to allocate this much memory.

check space optimised approach (shared above)

#5

sir i’m doint it with memorisation not by top down approach

#6

ok no issue ,try top down
image
here it should be
if(n==0){
return sum==0;
}

and increase ur dp size as per the constraint .

let me know what verdict u r getting

#7

/tmp/ccCfNDMA.o: in function __static_initialization_and_destruction_0(int, int)': source.cpp:(.text+0x323): relocation truncated to fit: R_X86_64_PC32 against .bss’
source.cpp:(.text+0x336): relocation truncated to fit: R_X86_64_PC32 against `.bss’
collect2: error: ld returned 1 exit status

#8

this typ of error is showing

#9

declare dp array this size -> image

#10

it working so can u plzzz explain base condition and size of dp array

#11

for size of dp check this constraint. i have declared size slightly greater than the given constraint so that it wont take much space.

if(n==0){
here we have two cases.
if(sum==0){ // traget sum exist
return true;
}else{ // i.e sum!=0
return false;
}
/*
above if else is equivalent to
return sum==0;
*/
}

#12

ok tnku sir one more doubt can i solve question with memorization or with top down approach which one is better and easy

#13

top down is easy and better because it is pure recursion (with one extra array to store calculated ans).

bottom is bit tricky and it takes too much practice to get a good grip over it.

#14

it means i’m in right track???

#15

yeah…
but also try bottom up approach .

#16

ok sir I’ll try if found any difficulty I reopen the doubt thanks a lot sir for clearing my doubt