【Subsets II】cpp

题目：

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

代码：

class Solution {

public:

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

            std::sort(nums.begin(), nums.end());

            vector<vector<int> > ret;

            vector<int> tmp;

            Solution::dfs(ret, nums, , tmp);

            return ret;

    }

    static void dfs(vector<vector<int> >& ret, vector<int>& nums, int index, vector<int>& tmp )

    {

            if ( index==nums.size() )

            {

                ret.push_back(tmp);

                return;

            }

            tmp.push_back(nums[index]);

            Solution::dfs(ret, nums, index+, tmp);

            tmp.pop_back();

            if ( !(tmp.size()>= && tmp.back()==nums[index]) )

            {

                Solution::dfs(ret, nums, index+, tmp);

            }

    }

};

tips：

大体思路与Subsets类似（http://www.cnblogs.com/xbf9xbf/p/4516802.html）

经过画图推演：dfs向左边走的条件不变；再向右边走时，如果当前节点的最后一个元素与即将要加入的新元素相同，则不往右边走了。因为再往右边走，右边肯定包含左边的重复子集了。

===================================

再补充一个增量构造法的迭代解法，代码如下：

class Solution {

public:

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {

            std::sort(nums.begin(), nums.end());

            vector<vector<int> > ret;

            vector<int> none;

            ret.push_back(none);

            int pureNew = ;

            for ( size_t i = ; i < nums.size(); ++i )

            {

                vector<vector<int> > tmp = ret;

                size_t begin = ;

                if ( i>= && nums[i]==nums[i-] )

                {

                    begin = ret.size()-pureNew;

                }

                for ( size_t j = begin; j < tmp.size(); ++j )

                {

                    tmp[j].push_back(nums[i]);

                    ret.push_back(tmp[j]);

                }

                pureNew = ret.size() - tmp.size();

            }

            return ret;

    }

};

tips:

增加新元素前，判断nums[i]==nums[i-1]的条件是否成立；如果成立，则增量应该只作用于上一轮新增加的子集上，这样保证没有重复的；这个思路也很简洁。

学习了几个blog的思路：

http://bangbingsyb.blogspot.sg/2014/11/leetcode-subsets-i-ii.html

http://www.cnblogs.com/TenosDoIt/p/3451902.html

http://www.cnblogs.com/yuzhangcmu/p/4211815.html

完毕。

============================================

第二次过这道题，只用dfs的写法。再次画画图，理解一下。

class Solution {

public:

        vector<vector<int> > subsetsWithDup(vector<int>& nums)

        {

            sort(nums.begin(), nums.end());

            vector<vector<int> > ret;

            vector<int> tmp;

            Solution::dfs(ret, nums, , tmp);

            return ret;

        }

        static void dfs(

            vector<vector<int> >& ret,

            vector<int>& nums, int index,

            vector<int>& tmp)

        {

            if ( index==nums.size() )

            {

                ret.push_back(tmp);

                return;

            }

            tmp.push_back(nums[index]);

            Solution::dfs(ret, nums, index+, tmp);

            tmp.pop_back();

            if ( !(tmp.size()> && tmp.back()==nums[index]) )

            {

                Solution::dfs(ret, nums, index+, tmp);

            }

        }

};

用深搜的好处就体现出来了。

巴特西

【Subsets II】cpp

最新文章

热门文章