codefun/Max_Sets_Without_Subsets.cpp at master · whodewho/codefun · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
Given a set S, find all the maximal subsets whose sum <= k. For example, if S = {1, 2, 3, 4, 5} and k = 7

Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

Hint:

- Output doesn’t contain any set which is a subset of other.

- If X = {1, 2, 3} is one of the solution then all the subsets of X {1} {2} {3} {1, 2} {1, 3} {2, 3} are omitted.

- Lexicographic ordering may be used to solve it
*/
#include <iostream>
#include <vector>
using namespace std;

void maxSubsetHelper(vector<vector<int> > &result, vector<bool> selected, vector<int> &numbers, int i, int k, int sum, int n)
{
    if(i==n)
    {
        int j=0;
        vector<int> row;
        for(;j<n;j++)
        {
            if(selected[j])row.push_back(numbers[j]);
            else if(numbers[j]+sum<=k)break;
        }
        if(j<n)return;
        result.push_back(row);
        return;
    }

    if(sum<=k)
    {
        maxSubsetHelper(result, selected, numbers, i+1, k, sum, n);
        if(sum+numbers[i]<=k)
        {
            selected[i]=true;
            maxSubsetHelper(result, selected, numbers, i+1, k, sum+numbers[i], n);
        }
    }
}

vector<vector<int> > maxSubsets(vector<int> numbers, int k)
{
    vector<vector<int> > result;
    int n=numbers.size();
    vector<bool> selected(n, false);
    maxSubsetHelper(result, selected, numbers, 0, k, 0, n);
    return result;
}

int main()
{
   int A[5]={1,2,3,4,5};
   vector<int> numbers(A, A+5);
   vector<vector<int> > result=maxSubsets(numbers, 7);
   for(int i=0;i<result.size();i++)
   {
        for(int j=0;j<result[i].size();j++)
            cout<<result[i][j]<<" ";
       cout<<endl;
   }
   cout << "Hello World" << endl;

   return 0;
}