Subsets.md

Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

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

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

这道题，让我们列出一个数组可能存在的所有情况。

解法：这道题需要一点小技巧。题目中的例子，实际上的变化过程可以是这样：[[]] => [[][]] => [[][1]] => [[][1][]] => [[][1][2]] => [[][1][2][1]] => [[][1][2][1, 2]] .... 看明白了吗？这里实际上可以先插入前面的元素，然后再补上当前循环到的元素则可以了，这里最主要的技巧就是这个了。

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res(1);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            int size = res.size();
            for (int j = 0; j < size; j++) {
                res.push_back(res[j]);
                res.back().push_back(nums[i]);
            }
        }

        return res;
    }
};

相似题目[Subsets II](./Subsets II.md)