Sharing my 8ms easy-understanding C++ recursion solution


  • 2

    The comments should be self-explanary, but the basic idea is in each recursion call, we removes the last element of the input numbers, and call subsets() on the remaining numbers, then adds back the last element to each of the subsets of the remaining numbers to construct the final result.

    e.g.
    nums = {3, 1, 2}
    sort -> nums = {1, 2, 3}
    last = 3
    remaining nums = {1, 2}
    call subsets(nums) -> {{}, {1}, {2}, {1, 2}}
    adds back last -> {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}.

    vector<vector<int>> subsets(vector<int>& nums) {
      vector<vector<int>> result;
    
      // recursion ending condition, we return an empty vector
      if (nums.size() <= 0) {
        result.push_back(nums);
        return result;
      }
    
      // sort the input numbers
      std::sort(nums.begin(), nums.end());
    
      // get the last element from the input numbers
      // this way we can make sure when we push back
      // in the recursive call, the biggest element are at the back
      int last = nums[nums.size() - 1];
      nums.erase(nums.end() - 1);
    
      // recursively construct the subsets
      for (vector<int> e : subsets(nums)) {
        result.push_back(e);
        e.push_back(last);
        result.push_back(e);
      }
    
      return result;
    }

Log in to reply
 

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