Comparisons of Codes for Subsets and Subsets II


  • 0

    Well, the codes are tremendously similar for Subsets and Subsets II. Simply taking a look at the following differences (the comment at the second piece of code).


    Subsets

    vector<vector<int>> subsets(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            vector<int> temp;
            res.push_back(temp);
            subsets_helper(nums, 0, nums.size(), temp, res);
            return res;
        }
        void subsets_helper(vector<int> nums, int pos, int n, vector<int> temp, vector<vector<int>> &res) {
            if (temp.size() == n) return;
            for (int j = pos; j < n; j++) {
                temp.push_back(nums[j]);
                res.push_back(temp);
                subsets_helper(nums, j + 1, n, temp, res);
                temp.pop_back();
            }
        }
    

    Subsets II

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> res;
            vector<int> temp; 
            res.push_back(temp);
            subsetWithDupHelper(nums, 0, nums.size(), temp, res);
            return res;
        }
        void subsetWithDupHelper(vector<int> nums, int pos, int n, vector<int> temp, vector<vector<int>>& res) {
            if (temp.size() == n) return;
            for (int i = pos; i < n; i++) {
                if (i == pos || nums[i] != nums[i - 1]) { // For preventing duplicates
                    temp.push_back(nums[i]);
                    res.push_back(temp);
                    subsetWithDupHelper(nums, i + 1, n, temp, res);
                    temp.pop_back();
                }
            }
        }

  • 0
    C

    Here is a comparison between Subsets and Subsets II in Python language:

    Subset

    def subsets(self, nums):
        res = []
        nums.sort()
        self.dfs(nums, 0, [], res)
        return res
        
    def dfs(self, nums, index, subSet, res):
        res.append(subSet)
        for i in xrange(index, len(nums)):
            self.dfs(nums, i+1, subSet+[nums[i]], res)
    

    Subset II

    def subsetsWithDup(self, nums):
        res = []
        nums.sort()
        self.dfs(nums, 0, [], res)
        return res
        
    def dfs(self, nums, index, sub, res):
        res.append(sub)
        for i in xrange(index, len(nums)):
            if i > index and nums[i] == nums[i-1]:
                continue
            self.dfs(nums, i+1, sub+[nums[i]], res)

  • 0

    Python codes are really concise :-)


  • 0
    C

    Yes, Python is cheating language~


Log in to reply
 

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