78. Subsets (Medium)

Posted on | In
  1. Subsets (Medium)

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. 递归回溯法

    每次在现有的集合下选择加入下一个元素，并把每次的过程都放在最终的result中，然后把下一个元素pop出来，在此情况下选择下下个元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    vector<vector<int>> res;
        vector<vector<int>> subsets(vector<int>& nums) {
            vector<int> temp;
            backtrack(nums, 0, temp);
            return res;
        }
        
        void backtrack(vector<int>& nums, int first, vector<int> temp){
            res.push_back(temp);
            for(int i = first; i<nums.size(); i++){
                temp.push_back(nums[i]);
                backtrack(nums, i+1, temp);
                temp.pop_back();
            }
        }

  1. 迭代：

    对于每一个nums[n]，分别加入res中已经组成的vector，并将新的vector加入到res中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    vector<vector<int>> subsets(vector<int>& nums) {
            vector<vector<int>> res;
            vector<int> temp;
            res.push_back({});
            for(int n=0; n<nums.size(); n++){
                int sz = res.size();
                for(int i=0; i<sz; i++){
                    temp = res[i];
                    temp.push_back(nums[n]);
                    res.push_back(temp);
                }
            }
            return res;
        }