Hello . I have a question and I want your help . Given N and a set containing N numbers we want to output all of the substes of the set . And the sum of the numbers of the subset
Example :
Input :
3
1 2 3
1 ----> 1
2 ----> 2
3 ----> 3
1 2 ----> 3
1 3 ----> 4
2 3 ----> 5
1 2 3 ----> 6
You've been posting a lot of questions lately, and I've been answering all of them, though this one seems to be very easy compared to the others. I'm not sure what solution exactly do you expect to see, this could be done with really just basic recursion.
As a parameter of the recursion we keep the number we are currently on, and then we simply have two choices — take it in the current subset, or not. Using that basic rule you can easily construct a solution to print all the sets. Keeping track of the sum is just really easy and can be done globally or by parameter. Here is a fully working code in C++ :
Obviously we have O(2^N) subsets as each number can either be picked or not in each subset, and also printing a subset takes roughly O(N), so very roughly the total complexity should be O(2^N * N), so obviously running it for more than 20 numbers should take some time.
Feel free to ask me if you don't understand something.
P.S. The program also counts the empty subset as a subset, but that just depends on the problem you are solving.
P.S.S. The program also doesn't print them in some specific order, however I assumed you want to know how to generate them rather than solving an actual problem requiring you to print them.