11. Combination

[bonfy]

Combination

[bonfy]

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> subsets(vector<int>& arr, int size) {
    vector<vector<int>> ans;

    int n = arr.size();

    for (int i=0; i<1<<n; i++) {
        vector<int> subset;
        cout << i << ":" << endl;
        for(int j=0; j<n; j++) {
            if(i&(1<<j)) {
                cout << i << " & " << (1<<j) << " = " << (i&(1<<j)) << endl;
                subset.push_back(arr[j]);
            }
        }
        cout << endl;
        if (size == -1) {
            ans.push_back(subset);
        } else {
            if (subset.size() == size) ans.push_back(subset);
        }
    }

    return ans;
}

int main() {
    vector<int> arr = {1,2,3,4,5};

    // All combination length is 3
    vector<vector<int>> ans = subsets(arr, 3);

    // All combination
    // vector<vector<int>> ans = subsets(arr, -1);
    for (auto x: ans) {
        cout << "{ ";
        for (auto m: x) cout << m << " ";
        cout << "}" << endl;
    }
    return 0;
}

[bonfy]

Recursive

# codint: utf-8

def subsets(n):
    if n == 0:
        return [[]]
    else:
        ans = subsets(n-1)
        return ans + [x+[n] for x in ans]

def subsets_arr(arr):
    if len(arr) == 0:
        return [[]]
    else:
        ans = subsets_arr(arr[:len(arr)-1])
        return ans + [x+[arr[-1]] for x in ans]

print(subsets(3))
print(subsets_arr([1,3,5]))