DFS + backtracking


  • 0
    N

    Time Complexity : O(n ^ k)
    Running Time: beat 75.71%

    vector<vector<int>> combine(int n, int k) {
        vector<int> combo;
        vector<vector<int>> res;
        if ( k <= 0 || n < 1 || n < k) return res;
        DFS(1, n, k, combo, res);
        return res;
    }
    
    void DFS(int pos, int n, int k, vector<int>& combo, vector<vector<int>>& res) {
        if (combo.size() > k) return;
        if (combo.size() == k) {
            res.push_back(combo);
            return;
        }
        
        for (int i = pos; i <= n; i++) {
            combo.push_back(i);
            DFS(i + 1, n, k, combo, res);
            combo.pop_back();
        }
    }
    

    Typical DFS + backtracking.
    lots of people are using DP on this problem. I don't think DP is good for this kind of combinatorial search. I don't see traditional DFS can produce duplicate subproblem, which is key point for DP application.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.