大数据

lintcode 第十七、十八题 子集和带重复数字的子集

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

class Solution {
public:
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    vector > subsets(vector &nums) {
        // write your code here
        //sort(nums.begin(),nums.end());
        vector > result;
        vector temp;
        subset(result,nums,temp,0);
        return result;
    }
    void subset(vector > &res,vector num,vector 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 > subsetsWithDup(const vector &S) {
        // write your code here
        vector > result;
        vector temp;
        vector nums(S);
        sort(nums.begin(),nums.end());
        subset(result,nums,temp,0);
        return result;
    }
    void subset(vector > &res,vector num,vector 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();
        }
    }
};