C++ Solution using DFS and Recursion 0ms O(n^k)


  • 0
    T
    class Solution {
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
            vector<vector<int>> result;
            vector<int> temp;
            int local = 0;
            dfs(result, temp, local, k, n, 1);
            return result;
        }
        
        void dfs(vector<vector<int>> &result, vector<int> &temp, int &local, int &k, int &n, int index) {
            if(temp.size() > k) {
                return;
            } 
            
            if(local == n && temp.size() == k) {
                result.push_back(temp);
                return;
            } 
            
            for(int i = index; i <= 9 && local <= n; i++) {
                temp.push_back(i);
                local += i;
                dfs(result, temp, local, k, n, i + 1);
                local -= i;
                temp.pop_back();
            }
        }
    };

  • -1
    M

    Why did you think it's O(n^k) time complexity?


  • 0
    T

    If you visualize the tree, it will have K levels (height). Each Node has an ability to have atmost n-1 childre. Hence O(n^k)


  • 0
    M

    I agree that the tree will have K levels, but not about children. Each tree node can have up to 9 children (because you've got up to 9 recursion calls) . So, tree levels will have at most 9, 99, ..., 9^k children respectively. So, in general up to O(k(9^k)) children in the tree. I think this is the complexity.


  • 0
    T

    Hi Marian, I agree. Sorry, when I said N^k I should've said 9^k. Also, don't you think it should be O(9* 9^k) = O(9^k)?


Log in to reply
 

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