Why bit manipulation method is slow than recursion method


  • 0
    W

    Bit manipulation solution

    class Solution {
        public:
            vector<vector<int>> subsets(vector<int>& nums) {
                sort(nums.begin(),nums.end());
                int max=1<<nums.size(),n=nums.size()-1;
                vector<vector<int>> result;
                for(int i=0;i<max;i++)
                {
                    int mask=1;
                    vector<int> vec;
                    for(int j=nums.size()-1;j>=0;j--)
                    {
                        if(i&(mask<<j)) vec.push_back(nums[n-j]);
                    }
                    result.push_back(vec);
                }
                return result;
            }
        };
    

    Recursion method

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(),nums.end());
            vector<vector<int>> result;
            if(nums.size() == 0)
                return result;
            vector<int> path;
            dfs(result,path,nums,0);
            return result;
            
        }
        
        void dfs(vector<vector<int>> & result, vector<int> &path, vector<int> & nums, int start){
            result.push_back(vector<int>(path));
            
            for(int i = start; i < nums.size(); i++){
                path.push_back(nums[i]);
                dfs(result,path,nums,i+1);
                path.pop_back();
            }
            
        }
    };
    

    The bit manipulation solution use 8ms, while the recursion solution use only 4ms. Why would that?


Log in to reply
 

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