leetcode_subsets

发表于

难度：Medium

解题思路：

比如[1,2,3],遍历每个元素，来组成插入的vector。我们可以将当前元素放入，也可以不放入。

1放、2放、3放：        1 2 3
1放、2放、3不放：    1 2
1放、2不放、3不放：    1
1不放、2放、3放：    2 3
1不放、2放、3不放：2
1不放、2不放、3放：    3
第三个不放：        []

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> cur_vec;
        get_sets(ret, cur_vec, nums, 0, nums.size()-1);
        return ret;
    }
    void get_sets(vector<vector<int>> &ret, vector<int>& current_vec,vector<int>& nums, int left, int right)
    {
        if(left > right)
        {
            ret.push_back(current_vec);
            return;
        }
        current_vec.push_back(nums[left]);
        get_sets(ret, current_vec, nums, left+1, right);
        current_vec.pop_back();
        get_sets(ret, current_vec, nums, left+1, right);
    }
};

运行结果：6ms，超过21.35%

另一种做法：

空：[]
1个元素:[] [1]
2个元素：[] [1] [2] [1, 2]
3个元素：[] [1] [2] [1, 2] [3] [1,3] [2,3] [1,2,3]
....

每次增加数组都是上一次数组的基础之上，加入新增加的值。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        ret.push_back(vector<int>());
        for(int i = 0; i < nums.size(); i++)
        {
            int sz = ret.size();
            for(int j = 0; j < sz; j++)
            {
                ret.push_back(ret[j]);
                ret.back().push_back(nums[i]);
            }
        }
        return ret;
    }
};

运行结果：6ms，超过21.35%

ref:http://www.cnblogs.com/grandyang/p/4309345.html