C++ two methods: recursive and DP


  • 0
    X
    class Solution {
    public:
        //DP 8ms
        //each time, we add the current number to all the subsets
        //then combine them to all the previous subsets
        /*
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> ret;
            ret.push_back(vector<int>());
            vector<vector<int>> sub;
            for(int i = 0; i < nums.size(); ++i){
                sub = ret;
                for(auto& j : sub){
                    j.push_back(nums[i]);//add
                }
                ret.insert(ret.end(), sub.begin(), sub.end());//combine
            }
            return ret;
        }
        */
        //recursive 8ms
        void generate(int depth, vector<int>& path, vector<vector<int>>& ans, vector<int>& nums){
            ans.push_back(path);
            for(int i = depth; i < nums.size(); ++i){
                path.push_back(nums[i]);
                generate(i + 1, path, ans, nums);
                path.pop_back();
            }
        }
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> ans;
            vector<int> path;
            generate(0, path, ans, nums);
            return ans;
        }
    };

Log in to reply
 

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