77. Combinations - cocoder39/coco39_LC GitHub Wiki

77. Combinations

Notes 2020:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        self.helper(n, k, 1, [], res)
        return res
        
    def helper(self, n, k, start, path, res):
        if len(path) == k:
            res.append(path[:])
            return
        
        if len(path) + n - (start - 1) < k:
            return
        
        for i in range(start, n+1):
            path.append(i)
            self.helper(n, k, i+1, path, res)
            path.pop()

Time complexity: count the number of result (i.e., C(N, K)) and number of operations on each element in each result (i.e., 3 one push, one pop, one copy to the final res). Total time complexity O(K * C(N, K))

=====================================================================================================================

once a number is chosen, helper() would run one time. Hence in total helper() would run C(k, n) times. Each time coping cur to res after generating a combination. Thus, the total time is O(k * C(k, n))

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> cur;
        helper(res, cur, n, 1, k);
        return res;
    }
private:
    void helper(vector<vector<int>>& res, vector<int>& cur, int n, int start, int k) {
        if (cur.size() == k) { 
            res.push_back(cur);
            return;
        }
        else if (cur.size() + n - start + 1 < k) { //optimization
            return;
        }
 
        for (int i = start; i <= n; i++) {
            cur.push_back(i);
            helper(res, cur, n, i + 1, k);
            cur.pop_back();
        }
    }
};
⚠️ **GitHub.com Fallback** ⚠️