lintcode 子集和带重复数字的子集

第十七题是给定一个不含重复数字的集合，返回其子集；十八题是给定一个可能有重复数字的集合，返回其子集。
先来说没有重复数字的情况
首先把空集合加进去，然后在循环里面进行递归调用，在进行递归时，将i的值加1，就可以排除前面已经加进去的数字，这道题可以和十五十六题进行比较，都属于深度优先搜索。代码如下：

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector<vector<int> > subsets(vector<int> &nums) {
        // write your code here
        //sort(nums.begin(),nums.end());
        vector<vector<int> > result;
        vector<int> temp;
        subset(result,nums,temp,0);
        return result;
    }
    void subset(vector<vector<int> > &res,vector<int> num,vector<int> temp,int i) {
        res.push_back(temp);
        for (i;i < num.size();i++) {
            temp.push_back(num[i]);
            subset(res,num,temp,i+1);
            temp.pop_back();
        }
    }
};

当有重复的数字时，为了避免产生重复的集合，就要进行去重操作，去重也很简单，只需要sort数组，让一样大小的重复的数字挨着，再加一个if判断就可以了。需要指出一点，和没有重复数字的递归函数有一个不一样，就是函数的参数，这里用了一个start，然后让i从start开始，这个start的目的就是在递归去掉重复的数字，因为在i-1有可能会越界。

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> temp;
        vector<int> nums(S);
        sort(nums.begin(),nums.end());
        subset(result,nums,temp,0);
        return result;
    }
    void subset(vector<vector<int> > &res,vector<int> num,vector<int> temp,int start) {
        res.push_back(temp);
        for (int i = start;i < num.size();i++) {
            if (i != start && num[i] == num[i-1]) continue;
            temp.push_back(num[i]);
            subset(res,num,temp,i+1);
            temp.pop_back();
        }
    }
};