C++ Non-recursive BFS with preallocation, 3ms


  • 0
    A

    Preallocate first and resize later.

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            uint n = nums.size();
            vector<vector<int>> v(1<<n, vector<int>(n+1));
            for (uint b = 0, p = 1, i = 0; i < n; i++) {
                for (uint e = p; b < e; v[b++].resize(i)) {
                    for (uint j = v[b][n]; j < n; p++) {
                        memcpy(&v[p].front(), &v[b].front(), i*sizeof(int));
                        v[p][i] = nums[j++];
                        if (i != n - 1) v[p][n] = j;
                        else v[p].resize(n);
                    }
                }
            }
            return v;
        }
    };
    

Log in to reply
 

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