Created
July 18, 2020 07:30
-
-
Save tamirazrab/38a3d356df599d790b60a95c08c4f3a0 to your computer and use it in GitHub Desktop.
Time complexity is same as it is in simple brute force approach not efficient according to run time.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <stdio.h> | |
| using namespace std; | |
| bool subSet( int ar[] , int sum, int size ) { | |
| int results [ size + 1 ] [ sum + 1 ]; | |
| // wmemset( &results [ 0 ] [ 0 ] , 0 , sizeof( results )); | |
| for( int i = 1; i < size + 1; ++i ) { | |
| for ( int j = 1; j < sum + 1; ++j ) { | |
| if ( ar [ i - 1 ] > j ) | |
| results [ i ] [ j ] = results [ i - 1 ] [ j ]; | |
| else if ( j >= ar [ i - 1 ]) | |
| results [ i ] [ j ] = results [ i - 1 ] [ j ] || results [ i - 1 ] [ j - ar [ i - 1 ] ]; | |
| } | |
| } | |
| return results [ size ] [ sum ]; | |
| } | |
| int main() { | |
| cout << "How many elements : "; | |
| int elements = 0; | |
| cin >> elements; | |
| int ar [ elements ]; | |
| for ( int i = 0; i < elements; ++i ) { | |
| cout << "Enter value for " << i + 1 << " : "; | |
| cin >> ar [ i ]; | |
| } | |
| int size = sizeof( ar ) / sizeof ( ar [ 0 ]); | |
| cout << "Enter sum required : "; | |
| int sum = 0; | |
| cin >> sum; | |
| if(subSet( ar, sum, size )) | |
| cout << "Subset exists which is equvalient to " << sum; | |
| else | |
| cout << "Subset doesn't exists which can give " << sum; | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment