subsets.md

Subsets

Given a set of distinct integers, S, 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 S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

这题其实就是列出集合里面的所有子集合，同时要求子集合元素需要升序排列。

首先我们需要对集合排序，对于一个n元素的集合，首先我们取第一个元素，加入子集合中，后面的n - 1个元素可以认为是第一个元素的子节点，我们依次遍历，譬如遍历到第二个元素的时候，后续的n - 2个元素又是第二个元素的子节点，再依次遍历处理，直到最后一个元素，然后回溯，继续处理。处理完第一个元素之后，我们按照同样的方式处理第二个元素。

譬如上面的[1, 2, 3]，首先取出1，加入子集合，后面的2和3就是1的子节点，先取出2，把[1, 2]加入子集合，后面的3就是2的子节点，取出3，把[1, 2, 3]加入子集合。然后回溯，取出3，将[1, 3]加入子集合。

1处理完成之后，我们可以同样方式处理2，以及3。

代码如下：

class Solution {
public:
    vector<vector<int> > res;
    vector<vector<int> > subsets(vector<int> &S) {
        if(S.empty()) {
            return res;
        }

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

        //别忘了空集合
        res.push_back(vector<int>());

        vector<int> v;

        generate(0, v, S);

        return res;
    }

    void generate(int start, vector<int>& v, vector<int> &S) {
        if(start == S.size()) {
            return;
        }

        for(int i = start; i < S.size(); i++) {
            v.push_back(S[i]);

            res.push_back(v);

            generate(i + 1, v, S);

            v.pop_back();
        }
    }
};

Subsets II

Given a collection of integers that might contain duplicates, S, 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 S = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

这题跟上题唯一的区别在于有重复元素，但是我们得到的子集合又不能有相同的，其实做法很简单，仍然按照上面的处理，只是遍历子节点的时候如果发现有相等的，只遍历一个，后续跳过。代码如下：

class Solution {
public:
    vector<vector<int> > res;

    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        if(S.empty()) {
            return res;
        }

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

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

        vector<int> v;

        generate(0, v, S);

        return res;
    }

    void generate(int start, vector<int>& v, vector<int> &S) {
        if(start == S.size()) {
            return;
        }

        for(int i = start; i < S.size(); i++) {
            v.push_back(S[i]);

            res.push_back(v);

            generate(i + 1, v, S);

            v.pop_back();

            //这里跳过相同的
            while(i < S.size() - 1 && S[i] == S[i + 1]) {
                i++;
            }
        }
    }
};