Share my several C++ solutions,easy to understand


  • 3
    V

    Solution(1):

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> ret;
            if (n == 0)
                return ret;
                
            sort(nums.begin(), nums.end());
            
            int i = 0, j = 0, len = 0;
            vector<int> temp;
            ret.push_back(temp);
            
            for (i = 0; i < n; i++)
            {
                len = ret.size();
                for (j = 0; j < len; j++)
                {
                    temp = ret[j];
                    temp.push_back(nums[i]);
                    ret.push_back(temp);
                }
            }
            
            return ret;
        }
    };
    

    Solution(2):using recursion

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> ret;
            vector<int> temp;
            
            if (n == 0)
                return ret;
                
            sort(nums.begin(), nums.end());
            
            subsetRecusion(nums, ret, temp, 0);
            
            return ret;
        }
        
        void subsetRecusion(vector<int>& nums, vector<vector<int>>& ret, vector<int> temp, int i)
        {
            if (i == nums.size())
            {
                ret.push_back(temp);
                return;
            }
            
            //there is no nums[i]
            subsetRecusion(nums, ret, temp, i+1);
            
            //there is nums[i]
            temp.push_back(nums[i]);
            subsetRecusion(nums, ret, temp, i+1);
        }
    };
    

    Solution(3):bit manipulation

    class Solution {
    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            int n = nums.size();
            vector<vector<int>> ret;
            if (n == 0)
                return ret;
                
            int total = 1 << n;
            int i = 0, j = 0, t = 0;
            
            sort(nums.begin(), nums.end());
            
            for (i = 0; i < total; i++)
            {
                vector<int> temp;
                t = i;
                j = 0;
                
                for (j = 0; j < n; j++)
                {
                    if (t == 0)
                        break;
                    if (t & 1)
                        temp.push_back(nums[j]);
                    
                    t = t >> 1;
                }
                
                ret.push_back(temp);
            }
            
            return ret;
        }
    };

Log in to reply
 

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