Skip to main content

Combination Problems

Combination containing k elements is a SUBSET containing k elements.

https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)

possible combinations of size=k​

Subsets having size() == k​

create all SUBSETs and then only add SUBSETs having size() == k

class Solution {
public:
    vector<vector<int>> ans;

    void foo(vector<int>& v,vector<int>& subset, int pos, int k) {
        if (subset.size() == k) {
            ans.emplace_back(subset);
        }
        for (int i=pos; i<v.size(); i++) {
            // NO duplicates are present here
            subset.emplace_back(v.at(i));
            foo(v, subset, i+1, k);
            subset.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<int> v;
        int sum = 0;
        for (int i=0; i<n; i++) {
            v.emplace_back(++sum); // 1,2,3...
        }

        vector<int> subset;
        int pos = 0;
        foo(v, subset, pos, k);

        return ans;
    }
};