lintcode-18-带重复元素的子集

带重复元素的子集

给定一个可能具有重复数字的列表，返回其所有可能的子集

注意事项

子集中的每个元素都是非降序的

两个子集间的顺序是无关紧要的

解集中不能包含重复子集

样例

如果 S = [1,2,2]，一个可能的答案为：

[

[2],

[1],

[1,2,2],

[2,2],

[1,2],

[]

]

挑战

你可以同时用递归与非递归的方式解决么？

标签

递归

code

class Solution {

public:

    /**

     * @param S: A set of numbers.

     * @return: A list of lists. All valid subsets.

     */

    vector<vector<int> > subsetsWithDup(const vector<int> &S) {

        // write your code here

        vector<vector<int> > result;

        vector<int> nums(S);

        int size = nums.size();

        if(size == 0) {

            result.push_back(vector<int> ());

            return result;

        }

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

        vector<int> temp;

        subset(result, nums, temp, 0, size);

        return result;

    }

    void subset(vector<vector<int> > &result, vector<int> nums, vector<int> temp, int begin, int end) {

        result.push_back(temp);

        for(int i=begin; i<end; i++) {

            if (i!=begin && nums[i] == nums[i-1])

                continue;

            temp.push_back(nums[i]);

            subset(result, nums, temp, i+1, end);

            temp.pop_back();

        }

    }

};

巴特西

lintcode-18-带重复元素的子集

带重复元素的子集

注意事项

样例

挑战

标签

code

最新文章

热门文章