78. Subsets

发表于 | 分类于

每日一题 2019 - 04 - 13

题目：

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解法：

这个题让找出给定数组的子集的集合，思路比较直观，就是深层遍历的问题，每次都对数组中的某一个元素做深层次的遍历，但是需要设置必要的条件，也即一定要保证当前待推入数组的大小不能超过给定数组的大小，也即为了保证遍历时候不越界。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> temp ;
        vector<int> now ;
        temp.push_back(now);
        fun(temp,now,nums,0);
        return temp ;
    }
    void fun(vector<vector<int>>& temp,vector<int>& now, vector<int> nums, int k)
    {
        if( k <= nums.size()){
            for(int i = k ; i < nums.size() ; i ++ )
            {
                now.push_back(nums[i]);
                temp.push_back(now);
                fun(temp,now,nums,i+1);
                now.pop_back();
            }
        }
    }
};
0%
undefined