moBmo's blog

By moBmo, 10 years ago, In English

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

Tags sub, set
  • Vote: I like it
  • -16
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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++ :


#include <stdio.h> #include <vector> using namespace std; vector<int> current_subset; int n; int nums[101]; void generate_subsets(int current_number,int current_sum) { if (current_number==n+1) ///we have a subset { int i; for (i=0;i<current_subset.size();i++) ///print the subset with its sum { printf("%d ",current_subset[i]); } printf("---> %d\n",current_sum); } else { ///if we choose to pick the number current_subset.push_back( nums[ current_number ] ); generate_subsets(current_number+1,current_sum+nums[ current_number ]); current_subset.pop_back(); ///if we choose to not pick the number generate_subsets(current_number+1,current_sum); } return; } int main() { int i; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d",&nums[i]); } generate_subsets(1,0); return 0; }

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.