C++ Non-recursive BFS with preallocation beats 100%


  • 0
    A

    Preallocate space and directly copy the identical part to avoid number by number generation.
    Still, not a fan of recursive. And it seems this is the only BFS solution so far.

    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            int m = n;
            for (uint i = 2, j = n; i <= k; i++) { m *= --j; m /= i; }
            vector<vector<int>> v(m, vector<int>(k));
            for (uint d = 1, i = 0; i < k; i++) {
                for (uint u = 0, m = d; u < m; u++) {
                    for (uint t = n - k + i + 1, j = i ? v[u][i-1] + 1 : 1; j <= t; j++) {
                        if (j == t) {
                            v[u][i] = j;
                        } else {
                            memcpy(&v[d].front(), &v[u].front(), i*sizeof(int));
                            v[d++][i] = j;
                        }
                    }
                }
            }
            return v;
        }
    };
    

    0_1475354924641_Clipboard.png


Log in to reply
 

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