Help with TLE in backtracking

help
,
1

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?

2

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

3

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?

4

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