Help with TLE in backtracking

Problem: Given two integers n and k , return all possible combinations of k numbers out of 1 … n .

class Solution {
    vector<vector<int>> ans;
    void comb(int i, int n, int k, vector<int> path) {
        if(path.size() == k)
        {
            ans.push_back(path);
            return;
        }
        if(i > n)
            return;
        comb(i+1,n,k,path);
        path.push_back(i);
        comb(i+1,n,k,path);
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> dummy;
        comb(1,n,k,dummy);
        return ans;
    }
};

This is my code, which gives TLE for the input n = 20 and k = 16. Can someone explain why and how to optimse this?

You are passing path by value every time which adds a factor of k, either make it global or pass by reference

Thank you!
Also, while passing by reference, I get an AC only when I do a pop_back() after the second call. I don’t see how that’s necessary. Can you explain?

Because when you return while having passed by value, you return to the original state of the vector without the element you’ve added. With a pass by reference, everything’s modifying the same vector, so you end up never removing the new element you add, even if you backtrack.

1 Like