Subset sum problem

#1

why this is not passing??

#2 
#include<iostream>
#include<unordered_map>
using namespace std;
int dp[1005][10005];
int solve(int i,int w,int arr[],int n)
{
	if(i==n)
	{
		if(w==0) return true;
		return false;
	}
   if(dp[i][w]!=-1)  return dp[i][w];
   int a=0;
   int b=0;
	if(w-arr[i]>=0) 
	{
		a=solve(i+1,w-arr[i],arr,n);
	}
	b=solve(i+1,w,arr,n);

	return dp[i][w]= (a||b);

}
int main() {
	int n;
	cin>>n;
	int target;
	cin>>target;
	int arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
    for(int i=0;i<1005;i++)
	for(int j=0;j<10005;j++)
	dp[i][j]=-1;

	if(solve(0,target,arr,n)==1) cout<<"Yes"; 
	 else  cout<<"No";
	return 0;
}

You had made the dimensions of the dp table small

#3

means??..i didnt understand

#4

range of w is till 1e5 and you have made dp table with w till 1005 only.

#5

but you made it 10^4 it is still small??

#6

Yes it worked though … i was just testing the answer on different dimensions. I didnt make it 1e5 becoz i thought 1000*100000 might cause memory limit exceeded but it worked none the less.

#7

but sir how my anser come correct after passing this solution…i checked test cases thetest case contain sum of order 103678 10^6 order…check test case 2 and clear it…

#8

yes but you had made dp[1005 ][1005] which means for the w part you are only considering weights till 1005 but the weights have a maximum value of 100000 which will not fit into 1005.

#9

but i am calculating for w==1005 in my function how it is passed please check test case sir…test case 2 its order of 10^6

#10

Sorry i cant check…if you could send it here it would be a great help.

#11

500 123722
89376 30879 92770 36908 47786 38328 85379 60485 16642 41414 2355 90020 68683 20052 97756 13919 80533 83419 89165 55729 5204 95361 2560 56422 65775 21523 22855 65116 74060 3128 13922 79795 34015 23051 33062 98160 61386 18449 75004 78035 76222 77366 84414 44912 13777 98530 75191 94317 98308 64363 66406 3519 76084 68973 59949 41866 6855 99163 6989 97274 2298 20918 77077 36320 60329 26498 50839 21722 61306 25850 16117 53888 19575 538 98807 33360 15427 90357 44036 13743 71080 26801 17269 47171 95781 93577 5396 2644 92747 12392 99925 95053 49669 93361 47732 10005 36219 98579 48087 97532 40788 80563 51427 60371 97460 66594 10090 12895 73310 70485 26645 60749 97294 60273 24279 9434 53858 29682 28437 46612 58433 44722 58024 8110 38090 5764 34474 90668 20702 98920 4560 77849 79490 72346 54579 76958 55299 64676 6212 28617 51521 32864 5725 48822 9496 30012 58263 63361 59701 86708 26333 18142 47789 716 42611 2238 22839 93444 92914 43548 92372 97481 37757 88221 69834 92343 65186 41493 57027 87757 70117 24907 36980 75849 73736 46484 22220 48358 9852 81929 51425 52544 16430 99221 53268 75400 1467 76114 68851 94388 36022 61230 8228 73786 65811 94421 66136 31004 35921 39522 18769 22397 64436 55756 14606 54531 18599 36833 2897 44811 35121 70681 97362 67910 69910 66989 43317 87736 59463 12176 98483 95492 89765 6718 85637 55583 17498 68132 2947 69779 7662 38075 8535 88457 10190 39500 59348 28797 76341 78604 73615 27821 49292 87336 95739 35561 54333 55415 23304 13803 67598 21794 25654 73723 44871 11298 29313 78729 79437 48619 48515 3458 86701 73409 8275 13251 12917 67630 42055 5617 62593 32029 33445 11892 19372 45543 47461 90064 966 87124 3874 84923 8926 45887 58653 70156 57192 87974 48892 52989 52952 13766 72806 39661 87183 81088 52919 16459 65077 11333 22083 27677 43369 55535 55929 79100 17438 19749 69172 18411 6880 89405 3341 32165 51652 62002 2329 25203 66335 67580 78199 19294 97706 67365 75314 1248 64812 44592 17714 29897 55932 39804 73933 15660 11698 46221 11120 29143 65977 96651 63913 89217 2415 67262 21389 54074 45623 40077 79285 11965 7665 73843 47618 5378 41215 39292 6633 6035 83891 40706 52291 56183 80517 42583 88202 8574 88812 99329 37725 71148 95987 17997 60372 14762 85266 81769 68843 47248 21853 48135 75572 45877 21986 23198 67614 79560 62497 90606 1954 62747 31319 54252 18937 28195 13195 23499 36777 2014 22835 90861 89521 35182 8865 49901 49951 10491 48029 18801 57746 86241 83296 33326 32126 21641 72883 99747 17560 51739 90361 19522 14493 38039 73781 49790 66242 86983 73296 3026 5356 12490 10246 94885 47679 19118 61145 13989 45968 9181 49150 3722 95429 32453 53407 43914 70453 26297 60021 88020 78043 66741 7549 8895 4787 97690 58692 71036 1032 31995 90421 6396 44493 674 17640 8531 36152 95144 22528 82127 4332 71685 2208 16120 20497 55622 60042 90957 98278 36422 95336 76328 3170 2893 85231 7964 16942 60282 95360 17981 92285 85788 40736 53137 2822 58383 61675 55333 53534 562 53819 74225

#12

this is the test case 2

#13

it was not working previously but it is working now after i increased the dimensions right ??

#14

yess but why??..it should give segment fault

#15

Yes you are right…but i think it might be due to that fact that during the recursive calls w never crosses the dp table’s dimensions. You can check that by printing the w values during each recursive call.

#16

sir i have started from w itself if w is 1000000 it will check this index for sure…please look into my code

#17

Sir can you clear it very bad doubt clearing done by you…

#18

Can you please ask it again on portal . I dont know the reason why is it working.

#19

sir i have started from w itself if w is 1000000 it will check this index for sure…please look into my code

This is my doubt