10ms C++ DFS Solution with explanation, very simple to understand


  • 1
    D
    void dfs(vector<int>& nums, int i, vector<int>& output, vector<vector<int>> &result) {
        if (i == nums.size()) {
            return;
        }
        for (int j = i; j<nums.size(); j++) {
            output.push_back(nums[j]);
            result.push_back(output);
            dfs(nums,j+1,output,result);
            output.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        // the question is asking for nondescending order, then we should sort it first
        sort(nums.begin(), nums.end());
        // the question asks us to print out all possible subsets. it can usually be solved DFS
        // the tree looks like this for 1,2,3
        //              root
        //           1    2     3
        //          2 3  3 
        //         3     
        vector<int> output;
        vector<vector<int>> result;
        result.push_back(output);
        dfs(nums, 0, output, result);
        return result;
    }

Log in to reply
 

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