Leetcode78、求子集

1、问题

已知一组数(其中无重复元素)，求这组数可以组成的所有子集。 结果中不可有无重复的子集。
例如: nums[] = [1, 2, 3]
结果为: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

2、算法思路

利用回溯方法生成子集，即对于每个元素，都有试探放入或不放入集合中的 两个选择:

• 选择放入该元素，递归的进行后续元素的选择，完成放入该元素后续所有元素 的试探;
• 之后将其拿出，即再进行一次选择不放入该元素，递归的进行后续元素的选择，完成不放入该元素后续所有元素的试探。

本来选择放入，再选择一次不放入的这个过程，称为回溯试探法。

例如:
元素数组: nums = [1, 2, 3, 4, 5,...] ，子集生成数组item[] = []
对于元素1，
选择放入item，item = [1]，继续递归处理后续[2,3,4,5,...]元素;item = [1,...]
选择不放入item，item = []，继续递归处理后续[2,3,4,5,...]元素;item = [...]

3、代码实现

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    vector< vector<int> > subsets (vector<int>& nums)
    {
        // 回溯法递归
        vector< vector<int> > result;
        vector<int> item;  // 回溯时，产生各个自己的数组
        result.push_back(item);  // 将空集push到result中
        generate(0, nums, item, result);
        return result;
    }
private:
    void generate(int i, vector<int>& nums,
            vector<int>& item,
            vector< vector<int> >& result)
    {
        if (i >= nums.size())
            return;

        item.push_back(nums[i]);  // 将当前元素压入
        result.push_back(item);

        generate(i + 1, nums, item, result);
        item.pop_back();
        generate(i + 1, nums, item, result);
    }
};
int main()
{
    Solution S;

    vector<int> nums;
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(3);

    vector< vector<int> > res = S.subsets(nums);

    for (int i = 0; i < res.size(); i ++)
    {
        cout << "[";
        for (int j = 0; j < res[i].size(); j ++)
        {
            cout << res[i][j] << ", ";
        }
        cout << "]";
        cout << endl;
    }
    return 0;
}